On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE

DOI10.1017/S0963548300001553zbMath0830.68068OpenAlexW2095782926MaRDI QIDQ4852431

Oleg Verbitsky

Publication date: 29 November 1995

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300001553

zbMATH Keywords

NP optimization problemsmulti-prover interactive proof systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Does co-NP have short interactive proofs ?
• Optimization, approximation, and complexity classes
• Quantifiers and approximation
• The Knowledge Complexity of Interactive Proof Systems
• On the Structure of Polynomial Time Reducibility
• Algebraic methods for interactive proof systems
• IP = PSPACE

This page was built for publication: On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE