Sanjeev Arora
Carsten Lund
Skip Abstract Section
Abstract
We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier accepts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verifier rejects every provided “proof” with probability at least 1/2. Our result builds upon and improves a recent result of Arora and Safra [1998] whose verifiers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length).
As a consequence, we prove that no MAX SNP-hard problem has a polynomial time approximation scheme, unless NP = P. The class MAX SNP was defined by Papadimitriou and Yannakakis [1991] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige et al. [1996] and Arora and Safra [1998] and show that there exists a positive ε such that approximating the maximum clique size in an N-vertex graph to within a factor of Nε is NP-hard.
- ARORA, S. 1994. Probabilistic checking of proofs and hardness of approximation problems. Ph.D dissertation. Univ. California, Berkeley, Berkeley, Calif. Available from http://www.cs.princeton. edu/-arora. Google Scholar
- ARORA, S. 1996. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Sciences. IEEE, New York, pp. 2-12. Google Scholar
- ARORA, S., BABAI, L., STERN, J., AND SWEEDYK, Z. 1997. The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54, 2 (Apr.), 317-331. Google ScholarDigital Library
- ARORA, S., AND LUND, C. 1996. Hardness of approximations. In Approximation Algorithms for NP-Hard Problems, D. Hochbaum, ed. PWS Publishing, Boston, Mass., pp. 339-446. Google Scholar
- ARORA, S., MOTWANI, R., SAFRA, S., SUDAN, M., AND SZEGEDY, M. 1992. PCP and approximation problems. Unpublished note.Google Scholar
- ARORA, S., AND SAFRA, S. 1998. Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, 1 (Jan.), 70-122. Google ScholarDigital Library
- ARORA, S., AND SUDAN, M. 1997. Improved low degree testing and its applications. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 485-495. Google Scholar
- AUSIELLO, G., D'ATRI, A., AND PROTASI, M. 1980a. Structure preserving reductions among convex optimization problems. J. Comput. Syst. Sci. 21, 136-153.Google ScholarCross Ref
- AUSIELLO, G., MARCHETTI-SPACCAMELA, A., AND PROTASI, M. 1980b. Towards a unified approach for the classification of NP-complete optimization problems. Theoret. Comput. Sci. 12, 83-96.Google ScholarCross Ref
- BABAI, L. 1985. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, pp. 421-429. Google Scholar
- BABAI, L. 1993. Transparent (holographic) proofs. In Proceedings of the lOth Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 665. Springer-Verlag, New York, pp. 525-534. Google Scholar
- BABAI, L., AND FORTNOW, L. 1991. Arithmetization: a new methods in structural complexity theory. Computat. Complex. 1, 41-66.Google ScholarCross Ref
- BABAI, L., FORTNOW, L., LEVIN, L., AND SZEGEDY, M. 1991a. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 21-31. Google Scholar
- BABAI, L., FORTNOW, L., AND LUND, C. 1991b. Non-deterministic exponential time has two-prover interactive protocols. Comptat. Complex. 1, 3-40.Google ScholarCross Ref
- BABAI, L., AND FRIEDL, K. 1993. On slightly superlinear transparaent proofs. Univ. Chicago Tech. Rep. CS-93-13. Google Scholar
- BABAI, L., AND MORAN, S. 1988. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36, 254-276. Google ScholarDigital Library
- BEAVER, D., AND FEIGENBAUM, J. 1990. Hiding instances in multioracle queries. In Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 415. Springer-Verlag, New York. Google Scholar
- BELLARE, M. 1993. Interactive proofs and approximation: Reductions from two provers in one round. In Proceedings of the 2nd Israel Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 266-274.Google Scholar
- BELLARE, M., COPPERSMITH, D., HASTAD, J., Kiwi, M., AND SUDAN, M. 1996. Linearity testing in characteristic two. IEEE Trans. Inf. Theory 42, 6 (Nov.), 1781-1795. Google ScholarCross Ref
- BELLARE, M., GOLDREICH, O., AND SUDAN, M. 1995/1998. Free bits, PCPs and non-approximability--towards tight results. SIAM J. Comput., to appear. (Preliminary version in Proceedings of the 36th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1995, pp. 422-431. Full version available as TR95-024 of ECCC, the Electronic Colloquium on Computational Complexity, http://www.eccc.uni-trier.de/eccc/.) Google Scholar
- BELLARE, M., GOLDWASSER, S., LUND, C., AND RUSSELL, A. 1993/1994. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, 1993, pp. 294-304. (See also errata sheet in Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. ACM, New York, 1994, p. 820.) Google Scholar
- BELLARE, M., AND ROGAWAY, P. 1993/1995. The complexity of approximating a nonlinear program. J. Math. Prog. B 69, 3 (Sept. 1995), 429-441. Also in Complexity of Numerical Optimization, P. M. Pardalos, ed. World Scientific, 1993. Google Scholar
- BELLARE, M., AND SUDAN, M. 1994. Improved non-approximability results. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 184-193. Google Scholar
- BEN-OR, M., GOLDWASSER, S., KILIAN, J., AND WIGDERSON, A. 1988. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, pp. 113-131. Google Scholar
- BERMAN, P., AND SCHNITGER, G. 1992. On the complexity of approximating the independent set problem. Inf. Comput. 96, 77-94. Google ScholarDigital Library
- BERN, M., AND PLASSMANN, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32, 171-176. Google ScholarCross Ref
- BLUM, M. 1991. Program checking. In Proceedings of FST&TCS. Lecture Notes in Computer Science, vol. 560. Springer-Verlag, New York, pp. 1-9. Google Scholar
- BLUM, A., JIANG, T., LI, M., TROMP, J., AND YANNAKAKIS, M. 1994. Linear approximation of shortest superstrings. J. ACM 41, 4 (July), 630-647. Google ScholarDigital Library
- BLUM, M., AND KANNAN, S. 1989. Designing programs that check their work. In Proceedings of the 21st Annual Symposium on the Theory of Computing (Seattle, Wash., May 15-17). ACM, New York, pp. 86-97. Google Scholar
- BLUM, M., LUBY, M., AND RUBINFELD, R. 1993. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 3 (Dec.), 549-595. Google ScholarDigital Library
- CAI, J., CONDON, A., AND LIPTON, R. 1994. PSPACE is provable by two provers in one round. J. Comput. Syst. Sci. 48, 1 (Feb.), 183-193. Google ScholarDigital Library
- COHEN, A., AND WIGDERSON, A. 1989. Dispersers, deterministic amplification, and weak random sources. In Proceedings of the 30th Annual Symposium on the Foundations of Computer Science. IEEE, New York.Google Scholar
- CONDON, A. 1991. The complexity of the max word problem, or the power of one-way interactive proof systems. In Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 480. Springer-Verlag, New York. Google Scholar
- CONDON, A., FEIGENBAUM, J., LUND, C., AND SHOR, P. 1993. Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 305-314. Google Scholar
- CONDON, A., FEIGENBAUM, J., LUND, C., AND SHOR, P. 1996. Random debaters and the hardness of approximating stochastic functions. SIAM J. Comput. 26, 2 (Apr.), 369-400. Google Scholar
- CooK, S. A. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (Shaker Heights, Ohio, May 3-5). ACM, New York, pp. 151-158. Google Scholar
- CRESCENZI, P., AND KANN, V. 1995. A compendium of NP optimization problems. Tech. Rep. SI/RR-95/02, Dipartimento di Scienze dell'Informazione, Uinversita di Roma "La Sapienza". The list is updated continuously. (The latest version is available by anonymous ftp from nada.kth.se, as Theory/Viggo-Kann/compendium.ps.Z.)Google Scholar
- DAHLHAUS, E., JOHNSON, D., PAPADIMITRIOU, C., SEYMOUR, P., AND YANNAKAKIS, M. 1994. The complexity of multiway cuts. SIAM J. Comput. 23, 4, 864-894. Google ScholarDigital Library
- DE LA VEGA, W., AND LUEKER, G. 1981. Bin packing can be solved within 1 + # in linear time. Combinatorica 1, 349-355.Google ScholarCross Ref
- FAGIN, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Com-plexity of Computation, Richard Karp, ed. American Mathematical Society, Providence, R.I.Google Scholar
- FEIGE, U. 1996. A threshold of In n for set cover. In Proceedings of the 28th Annual Symposium on the Theory of Computing (Philadelphia, Pa., May 22-24). ACM, New York, pp. 314-318. Google Scholar
- FEIGE, U., GOLDWASSER, S., LOVASZ, L., SAFRA, S., AND SZEGEDY, M. 1996. Interactive proofs and the hardness of approximating cliques. J. ACM 43, 2 (Mar.), 268-292. Google ScholarDigital Library
- FEIGE, U., AND KILIAN, J. 1994. Two prover protocols--Low error at affordable rates. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 172-183. Google Scholar
- FEIGE, U., AND KILIAN, J. 1996. Zero knowledge and chromatic number. In Proceedings of the llth Annual Conference on Complexity Theory. IEEE, New York. Google Scholar
- FEIGE, U., AND LOVASZ, L. 1992. Two-prover one-round proof systems: Their power and their problems. In Proceedings of the 24th Annual Symposium on the Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 733-744. Google Scholar
- FORTNOW, L., ROMPEL, J., AND SIPSER, M. 1994. On the power of multi-prover interactive protocols. Theoret. Comput. Sci. 134, 2 (Nov.), 545-557. Google ScholarDigital Library
- FRIEVALDS, R. 1979. Fast probabilistic algorithms. In Proceedings of Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 74. Springer-Verlag, New York, pp. 57-69.Google Scholar
- FRIEDL, K., HATSAGI, ZS., AND SHEN, A. 1994. Low-degree testing. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York. Google Scholar
- FRIEDL, K., AND SUDAN, M. 1995. Some improvements to low-degree tests. In Proceedings of the 3rd Israel Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 250-260. Google Scholar
- FURER, M. 1995. Improved hardness results for approximating the chromatic number. In Proceed-ings of the 36th Annual Symposium on the Foundations of Computer Science. IEEE, New York. Google Scholar
- GAREY, M., AND JOHNSON, D. 1976. The complexity of near-optimal graph coloring. J. ACM 23, 1 (Jan.), 43-49. Google ScholarDigital Library
- GAREY, M., AND JOHNSON, D. 1978. "Strong" NP-completeness results: Motivation, examples and implications. J. ACM 25, 499-508. Google ScholarDigital Library
- GAREY, M., AND JOHNSON, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York. Google Scholar
- GAREY, M., JOHNSON, D., AND STOCKMEYER, L. 1976. Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1,237-267.Google ScholarCross Ref
- GEMMELL, P., AND SUDAN, M. 1992. Highly resilient correctors for polynomials. Inf. Proc. Lett. 43, 4 (Sept.), 169-174. Google ScholarDigital Library
- GEMMELL, P., LIPTON, R., RUBINFELD, R., SUDAN, M., AND WIGDERSON, A. 1991. Self-testing/ correcting for polynomials and for approximate functions. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 32-42. Google Scholar
- GOEMANS, M., AND WILLIAMSON, D. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 6 (Nov.), 1115-1145. Google ScholarDigital Library
- GOLDREICH, O. 1997. A taxonomy of proof systems. In Complexity Theory Retrospective H, L. A. Hemaspaandra and A. Selman, eds. Springer-Verlag, New York. Google Scholar
- GOLDWASSER, S., MICALI, S., AND RACKOFF, C. 1989. The knowledge complexity of interactive proof-systems. SIAM J. Comput. 18, 1 (Feb.), 186-208. Google ScholarDigital Library
- GRAHAM, R. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.Google ScholarCross Ref
- H/#kSTAD, J. 1996a. Testing of the long code and hardness for clique. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, Pa., May 22-24). ACM, New York, pp. 11-19. Google Scholar
- H/#kSTAD, J. 1996b. Clique is hard to approximate within n1-E In Proceedings of the 37th Annual Symposium on the Foundations of Computer Science. IEEE, New York. Google Scholar
- H/#kSTAD, J. 1997. Some optimal inapproximability results. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 1-10. Google Scholar
- IBARRA, O., AND KIM, C. 1975. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463-468. Google ScholarDigital Library
- IMPAGLIAZZO, R., AND ZUCKERMAN, D. 1989. How to recycle random bits. In Proceedings of the 30th Annual Symposium on the Foundations of Computer Science. IEEE, New York.Google Scholar
- JOHNSON, D. 1974. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256-278.Google ScholarDigital Library
- KANN, V. 1991. Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Proc. Lett. 37, 27-35. Google ScholarDigital Library
- KARGER, D., MOTWANI, R., AND RAMKUMAR, G. 1997. On approximating the longest path in a graph. Algorithmica 18, 1 (May), 82-98.Google ScholarDigital Library
- KARMAKAR, N., AND KARP, R. 1982. An efficient approximation scheme for the one-dimensional bin packing problem. In Proceedings of the 23rd Annual Symposium on the Foundations of Computer Science. IEEE. New York.Google Scholar
- KARP, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, ed. Advances in Computing Research. Plenum Press, New York, pp. 85-103.Google Scholar
- KHANNA, S., LINIAL, N., AND SAFRA, S. 1993. On the hardness of approximating the chromatic number. In Proceedings of the 2nd Israel Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 250-260.Google ScholarCross Ref
- KHANNA, S., MOTWANI, R., SUDAN, M., AND VAZIRANI, U. 1994/1998. On syntactic versus computational views of approximability. In Proceedings of the 35th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1994, pp. 819-830. (Also, SIAM J. Comput., to appear.)Google ScholarDigital Library
- KOLAITIS, P., AND VARDI, M. 1987. The decision problem for the probabilities of higher-order properties. In Proceedings of the 19th Annual Symposium on the Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 425-435. Google Scholar
- LAPIDOT, D., AND SHAMIR, A. 1997. Fully parallelized multi-prover protocols for NEXP-tie. J. Comput. Syst. Sci. 54, 2 (Apr.), 215-220. Google ScholarDigital Library
- LEVIN, L. 1973. Universarnyie perebornyie zadachi (Universal Search Problems: in Russian). Problemy Peredachi Informatsii 9, 3, 265-266. (A corrected English translation appears in an appendix to Trakhtenbrot {1984}.)Google Scholar
- LIPTON, R. 1991. New directions in testing. In Distributed Computing and Cryptography, vol. 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, J. Feigenbaum and M. Merritt, eds. American Mathematical Society, Providence, R. I., pp. 191-202.Google Scholar
- LUND, C., FORTNOW, L., KARLOFF, H., AND NISAN, N. 1992. Algebraic methods for interactive proof systems. J. ACM 39, 859-868. Google ScholarDigital Library
- LUND, C., AND YANNAKAKIS, M. 1993. The approximation of maximum subgraph problems. In Proceedings of ICALP 93, Lecture Notes in Computer Science, vol. 700. Springer-Verlag, New York. Google Scholar
- LUND, C., AND YANNAKAKIS, M. 1994. On the hardness of approximating minimization problems. J. ACM 41, 5 (Sept.), 960-981. Google ScholarDigital Library
- MITCHELL, J. 1998. Guillotine subdivisions approximate polygonal subdivision: Part II - A simple PTAS for geometric k-MST, TSP, and related problems. SIAM J. Comput., to appear. Google Scholar
- MOTWANI, R. 1992. Tech. Rep. Department of Computer Science, Stanford Univ., Stanford, Calif. In Lecture Notes on Approximation Algorithms, Springer-Verlag, New York. Google Scholar
- PAPADIMITRIOU, C., AND YANNAKAKIS, M. 1991. Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43, 425-440.Google ScholarCross Ref
- PAPADIMITRIOU, C., AND YANNAKAKIS, M. 1993. The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1-11. Google ScholarCross Ref
- PAZ, A., AND MORAN, S. 1981. Non-deterministic polynomial optimization problems and their approximation. Theoret. Comput. Sci. 15, 251-277.Google ScholarCross Ref
- PHILLIPS, S., AND SAFRA, S. 1992. PCP and tighter bounds for approximating MAXSNP. Manuscript. Stanford Univ., Stanford, Calif.Google Scholar
- POLISHCHUK, A., AND SPIELMAN, D.A. 1994. Nearly linear size holographic proofs. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 194-203. Google Scholar
- RAZ, R. 1995. A parallel repetition theorem. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 447-456. Google Scholar
- RAZ, R., AND SAFRA, S. 1997. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 475-484. Google Scholar
- RUBINFELD, R. 1990. A mathematical theory of self-checking, self-testing and self-correcting programs. Ph.D. dissertation. Univ. California, Berkeley, Berkeley, Calif. Google Scholar
- RUBINFELD, R., AND SUDAN, M. 1996. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25, 2 (Apr.), 252-271. Google ScholarDigital Library
- SAHNI, S. 1975. Approximate algorithms for the 0/1 knapsack problem. J. ACM 22, 115-124. Google ScholarDigital Library
- SAHNI, S., AND GONZALEZ, T. 1976. P-complete approximation problems. J. ACM 23, 555-565. Google ScholarDigital Library
- SCHWARTZ, J. 1980. Probabilistic algorithms for verification of polynomial identities. J. ACM 27, 701-717. Google ScholarDigital Library
- SHAMIR, A. 1992. IP = PSPACE. J. ACM 39, 4 (Oct.), 869-877. Google ScholarDigital Library
- SUDAN, M. 1992/1996. Efficient checking of polynomials and proofs and the hardness of approximation problems. Ph.D. dissertation. Univ. California, Berkeley, Berkeley, Calif., 1992. Also appears as ACM Distinguished Theses. In Lecture Notes in Computer Science, vol. 1001. Springer- Verlag, New York, 1996. Google Scholar
- TARDOS, G. 1994. Multi-prover encoding schemes and three prover proof systems. In Proceedings of the 9th Annual Conference on Structure in Complexity Theory. IEEE, New York.Google Scholar
- TRAKHTENBROT, B. 1984. A survey of Russian approaches to Perebor (brute-force search) algorithms. Ann. Hist. Comput. 6, 384-400.Google ScholarDigital Library
- WELCH, L., AND BERLEKAMP, E. 1986. Error correction of algebraic block codes. US Patent Number 4,633,470.Google Scholar
- YANNAKAKIS, M. 1994. On the approximation of maximum satisfiability. J. Algorithms 17, 3 (Nov.), 475-502. Google ScholarDigital Library
- ZUCKERMAN, D. 1996. On unapproximable versions of NP-complete problems. SIAM J. Comput. 25, 6 (Dec.), 1293-1304. Google ScholarDigital Library
Index Terms
- Proof verification and the hardness of approximation problems
Recommendations
Proof verification and hardness of approximation problems
SFCS '92: Proceedings of the 33rd Annual Symposium on Foundations of Computer ScienceThe class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y ...
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational ComplexityThe Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...
Comments