Free bits, PCPs and non-approximability-towards tight results
- 19 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2 (24) , 422-431
- https://doi.org/10.1109/sfcs.1995.492573
Abstract
The first part of this paper presents new proof systems and improved non-approximability results. In particular we present a proof system for NP using logarithmic randomness and two amortized free bits, so that Max clique is hard within N/sup 1/3/ and chromatic number within N/sup 1/5/. We also show hardness of 38/37 for Max-3-SAT, 27/26 for vertex cover, 82/81 for Max-cut, and 94/93 for Max-2-SAT. The second part of this paper presents a "reverse" of the FGLSS connection by showing that an NP-hardness result for the approximation of Max clique to within a factor of N/sup 1/(g+1/) would imply a probabilistic verifier for NP with logarithmic randomness and amortized free-bit complexity g. We also show that "existing techniques" won't yield proof systems of less than two bits in amortized free bit complexity. Finally, we initiate a comprehensive study of PCP and FPCP parameters, proving several triviality results and providing several useful transformations.Keywords
This publication has 22 references indexed in Scilit:
- NP-complete problems have a version that's hard to approximatePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximating clique is almost NP-completePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A parallel repetition theoremPublished by Association for Computing Machinery (ACM) ,1995
- Two prover protocolsPublished by Association for Computing Machinery (ACM) ,1994
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Multi-prover interactive proofs: how to remove intractabilityPublished by Association for Computing Machinery (ACM) ,1988
- The complexity of promise problems with applications to public-key cryptographyInformation and Control, 1984