Reductions, codes, PCPs, and inapproximability
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 404-413
- https://doi.org/10.1109/sfcs.1995.492571
Abstract
Many recent results show the hardness of approximating NP-hard functions. We formalize, in a very simple way, what these results involve: a code-like Levin reduction. Assuming a well-known complexity assumption, we show that such reductions cannot prove the NP-hardness of the following problems, where /spl epsiv/ is any positive fraction: (i) achieving an approximation ratio n/sup 1/2+/spl epsiv// for Clique, (ii) achieving an approximation ratio 1.5+/spl epsiv/ for Vertex Cover, and (iii) coloring a 3-colorable graph with O(logn) colors. In fact, we explain why current reductions cannot prove the NP-hardness of coloring 3-colorable graphs with 9 colors. Our formalization of a code-like reduction, together with our justification of why such reductions are natural, also clarifies why current proofs of inapproximability results use error-correcting codes.Keywords
This publication has 20 references indexed in Scilit:
- 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
- Improved non-approximability resultsPublished by Association for Computing Machinery (ACM) ,1994
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- One-way functions are necessary and sufficient for secure signaturesPublished by Association for Computing Machinery (ACM) ,1990
- On the complexity of approximating the independent set problemPublished by Springer Nature ,1989
- Matching is as easy as matrix inversionCombinatorica, 1987
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971