Proof verification and the hardness of approximation problems

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 &egr; such that approximating the maximum clique size in an N-vertex graph to within a factor of N&egr; is NP-hard.

REFERENCES

• 1: Sanjeev Arora, Probabilistic checking of proofs and hardness of approximation problems, University of California at Berkeley, Berkeley, CA, 1995
• 2: S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
• 3: Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
• 4: Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 5: ARORA, S., MOTWANI, R., SAFRA, S., SUDAN, M., AND SZEGEDY, M. 1992. PCP and approximation problems. Unpublished note.
• 6: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 7: Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258642]
• 8: AUSIELLO, G., D'ATRI, A., AND PROTASI, M. 1980a. Structure preserving reductions among convex optimization problems. J. Comput. Syst. Sci. 21, 136-153.
• 9: 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.
• 10: L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
• 11: László Babai, Transparent (Holographic) Proofs, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.525-534, February 25-27, 1993
• 12: BABAI, L., AND FORTNOW, L. 1991. Arithmetization: a new methods in structural complexity theory. Computat. Complex. 1, 41-66.
• 13: László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
• 14: BABAI, L., FORTNOW, L., AND LUND, C. 1991b. Non-deterministic exponential time has two-prover interactive protocols. Comptat. Complex. 1, 3-40.
• 15: Laszlo Babai , Katalin Friedl, On slightly superlinear transparent proofs, University of Chicago, Chicago, IL, 1993
• 16: László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
• 17: Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
• 18: 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.
• 19: 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.
• 20: M. Bellare , O. Goldreich , M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.422, October 23-25, 1995
• 21: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 22: Mihir Bellare , Phillip Rogaway, The complexity of approximating a nonlinear program, Mathematical Programming: Series A and B, v.69 n.3, p.429-441, Sept. 28, 1995 [doi>10.1007/BF01585569]
• 23: Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195129]
• 24: Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
• 25: Piotr Berman , Georg Schnitger, On the complexity of approximating the independent set problem, Information and Computation, v.96 n.1, p.77-94, Jan. 1992 [doi>10.1016/0890-5401(92)90056-L]
• 26: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2]
• 27: Manuel Blum, Program Checking, Proceedings of the 11th Conference on Foundations of Software Technology and Theoretical Computer Science, p.1-9, December 17-19, 1991
• 28: Avrim Blum , Tao Jiang , Ming Li , John Tromp , Mihalis Yannakakis, Linear approximation of shortest superstrings, Journal of the ACM (JACM), v.41 n.4, p.630-647, July 1994 [doi>10.1145/179812.179818]
• 29: M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
• 30: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 31: Jin-Yi Cai , Anne Condon , Richard J. Lipton, PSPACE is provable by two provers in one round, Journal of Computer and System Sciences, v.48 n.1, p.183-193, Feb. 1994 [doi>10.1016/S0022-0000(05)80026-1]
• 32: 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.
• 33: Anne Condon, The complexity of the max word problem and the power of one-way interactive proof systems, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.456-465, February 1991, Hamburg, Germany
• 34: Anne Condon , Joan Feigenbaum , Carsten Lund , Peter Shor, Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.305-314, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167190]
• 35: Anne Condon , Joan Feigenbaum , Carsten Lund , Peter Shor, Random Debaters and the Hardness of Approximating Stochastic Functions, SIAM Journal on Computing, v.26 n.2, p.369-400, April 1997 [doi>10.1137/S0097539793260738]
• 36: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 37: 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.)
• 38: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
• 39: DE LA VEGA, W., AND LUEKER, G. 1981. Bin packing can be solved within 1 + # in linear time. Combinatorica 1, 349-355.
• 40: 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.
• 41: Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237977]
• 42: Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
• 43: Uri Feige , Joe Kilian, Two prover protocols: low error at affordable rates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.172-183, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195128]
• 44: Uriel Feige , Joe Kilian, Zero Knowledge and the Chromatic Number, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.278, May 24-27, 1996
• 45: Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
• 46: Lance Fortnow , John Rompel , Michael Sipser, On the power of multi-prover interactive protocols, Theoretical Computer Science, v.134 n.2, p.545-557, Nov. 21, 1994 [doi>10.1016/0304-3975(94)90251-8]
• 47: 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.
• 48: Katalin Friedl , Zsolt Hátsági , Alexander Shen, Low-degree tests, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.57-64, January 23-25, 1994, Arlington, Virginia, United States
• 49: Some improvements to total degree tests, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.190, January 04-06, 1995
• 50: M. Furer, Improved hardness results for approximating the chromatic number, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.414, October 23-25, 1995
• 51: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• 52: M. R. Garey , D. S. Johnson, `` Strong '' NP-Completeness Results: Motivation, Examples, and Implications, Journal of the ACM (JACM), v.25 n.3, p.499-508, July 1978 [doi>10.1145/322077.322090]
• 53: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 54: GAREY, M., JOHNSON, D., AND STOCKMEYER, L. 1976. Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1,237-267.
• 55: Peter Gemmell , Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters, v.43 n.4, p.169-174, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90195-2]
• 56: Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
• 57: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 58: Oded Goldreich, A taxonomy of proof systems, Complexity theory retrospective II, Springer-Verlag New York, Inc., New York, NY, 1998
• 59: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 60: GRAHAM, R. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.
• 61: Johan Håstad, Testing of the long code and hardness for clique, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.11-19, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237820]
• 62: J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
• 63: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 64: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 65: 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.
• 66: JOHNSON, D. 1974. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256-278.
• 67: Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, v.37 n.1, p.27-35, Jan. 10, 1991 [doi>10.1016/0020-0190(91)90246-E]
• 68: KARGER, D., MOTWANI, R., AND RAMKUMAR, G. 1997. On approximating the longest path in a graph. Algorithmica 18, 1 (May), 82-98.
• 69: 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.
• 70: 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.
• 71: 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.
• 72: 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.)
• 73: P. Kolaitis , M. Vardi, The decision problem for the probabilities of higher-order properties, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.425-435, January 1987, New York, New York, United States [doi>10.1145/28395.28441]
• 74: Dror Lapidot , Adi Shamir, Fully parallelized multi-prover protocols for NEXP-time, Journal of Computer and System Sciences, v.54 n.2, p.215-220, April 1997 [doi>10.1006/jcss.1997.1238]
• 75: 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}.)
• 76: 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.
• 77: Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
• 78: Carsten Lund , Mihalis Yannakakis, The Approximation of Maximum Subgraph Problems, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.40-51, July 05-09, 1993
• 79: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 80: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 81: Rajeev Motwani, Lecture notes on approximation algorithms: Volume I, Stanford University, Stanford, CA, 1993
• 82: PAPADIMITRIOU, C., AND YANNAKAKIS, M. 1991. Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43, 425-440.
• 83: Christos H. Papadimitriou , Mihalis Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, v.18 n.1, p.1-11, Feb. 1993 [doi>10.1287/moor.18.1.1]
• 84: PAZ, A., AND MORAN, S. 1981. Non-deterministic polynomial optimization problems and their approximation. Theoret. Comput. Sci. 15, 251-277.
• 85: PHILLIPS, S., AND SAFRA, S. 1992. PCP and tighter bounds for approximating MAXSNP. Manuscript. Stanford Univ., Stanford, Calif.
• 86: Alexander Polishchuk , Daniel A. Spielman, Nearly-linear size holographic proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.194-203, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195132]
• 87: Ran Raz, A parallel repetition theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.447-456, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225181]
• 88: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 89: Ronitt A. Rubinfeld, A mathematical theory of self-checking, self-testing and self-correcting programs, University of California at Berkeley, Berkeley, CA, 1991
• 90: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 91: Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]
• 92: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 93: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 94: Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
• 95: Madhu Sudan, Efficient checking of polynomials and proofs and the hardness of approximation problems, University of California at Berkeley, Berkeley, CA, 1992
• 96: 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.
• 97: TRAKHTENBROT, B. 1984. A survey of Russian approaches to Perebor (brute-force search) algorithms. Ann. Hist. Comput. 6, 384-400.
• 98: WELCH, L., AND BERLEKAMP, E. 1986. Error correction of algebraic block codes. US Patent Number 4,633,470.
• 99: Mihalis Yannakakis, On the approximation of maximum satisfiability, Journal of Algorithms, v.17 n.3, p.475-502, Nov. 1994
• 100: David Zuckerman, On Unapproximable Versions of NP-Complete Problems, SIAM Journal on Computing, v.25 n.6, p.1293-1304, Dec. 1996 [doi>10.1137/S0097539794266407]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Theory

Keywords:
NP-completeness, optimization, proof verification, randomness