article

Free access

Probabilistic checking of proofs: a new characterization of NP

Authors:

Shmuel SafraAuthors Info & Claims

Journal of the ACM (JACM), Volume 45, Issue 1

Pages 70 - 122

https://doi.org/10.1145/273865.273901

Published: 01 January 1998 Publication History

Abstract

We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof.

We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.

References

[1]

AJTAI, M., KOMLOS, J., AND SZEMEREDI, E. 1987. Deterministic simulation in LOGSPACE. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 132-140.

[2]

ALON, N., GOLDREICH, O., HASTAD, J., AND PERALTA, R. 1992. Simple constructions of almost k-wise independent random variables. Rand. Struct. Algor. 3, 3, 289-304.

[3]

ARORA, S., BABAI, L., STERN, J., AND SWEEDYK, Z. 1993. The hardness of approximate optima in lattices, codes and linear equations. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 724-733.

[4]

ARORA, S., AND LUND, C. 1996. Hardness of approximations. Chapter 10 in Approximation Algorithms for NP-hard Problems, Dorit Hochbaum, ed. PWS Publishing.

[5]

ARORA, S., LUND, C., MOTWANI, R., SUDAN, M., AND SZEGEDY, M. 1992a. Proof verification and intractability of approximation problems. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 13-22.

[6]

ARORA, S., MOTWANI, R., SAFRA, M., SUDAN, M., AND SZEGEDY, M. 1992b. PCP and approximation problems. Manuscript.

[7]

ARORA, S., AND SAFRA, S. 1992. Probabilistic checking of proofs: A new characterization of NP. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 2-12.

[8]

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, ACM, New York, pp. 496-505.

[9]

BABAI, L. 1985. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, pp. 421-429.

[10]

BABAI, L., FORTNOW, L., LEVIN, L., AND SZEGEDY, M. 1991a. Checking computations in polylogarithmic time. In Proceedings of the 23rd ACM Symposium on Theory of Computing (New Orleans, La., May 6-8). ACM, New York, pp. 21-31.

[11]

BABAI, L., FORTNOW, L., AND LUND, C. 1991b. Non-deterministic exponential time has two-prover interactive protocols. Comput. Comp. 1, 3-40.

[12]

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 Press, New York, pp. 266-274.

[13]

BELLARE, M., GOLDREICH, 0., AND SUDAN, M. 1995. Free bits and nonapproximability: Towards tight results. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 422-431.

[14]

BELLARE, M., GOLDWASSER, S., LUND, C., AND RUSSELL, A. 1993. Efficient probabilistically checkable proofs with applications to approximation. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 113-131. (Errata in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, p. 820.)

[15]

BELLARE, M., AND ROGAWAY, P. 1993. The complexity of approximating nonlinear programs. In Complexity of Numerical Optimization, P. M. Pardalos, ed. World Scientific.

[16]

BELLARE, M., AND SUDAN, M. 1994. Improved non-approximability results. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 184-193.

[17]

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-121.

[18]

BERLEKAMP, E., AND WELCH, L. 1986. Error correction of algebraic block codes. US Patent Number 4,633,470.

[19]

BLUM, M., AND KANNAN, S. 1989. Designing programs that check their work. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (Seattle, Wash., May 15-17). ACM, New York, pp. 86-97.

[20]

BLUM, M., LUBY, M., AND RUBINFELD, R. 1990. Self-testing/correcting with applications to numerical problems. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, Md., May 12-14). ACM, New York, pp. 73-83.

[21]

BOPPANA, R., AND HALLDORSSON, M. 1992. Approximating maximum independent sets by excluding subgraphs. BIT 32, 180-196.

[22]

CHANG, R., CHOR, B., GOLDREICH, 0., HARTMANIS, J., HASTAD, J., RANJAN, D., AND ROHATGI, P. 1994. The random oracle hypothesis is false. J. Comput. Syst. Sci. 49, 1.

[23]

CHOR, B., AND GOLDREICH, 0. 1989. On the power of two-point based sampling. J. Complex. 5, 96-106.

[24]

CONDON, A. 1993. The complexity of the max-word problem and the power of one-way interactive proof systems. Computat. Complex. 3, 292-305.

[25]

CONDON, A., FEIGENBAUM, J., LUND, C., AND SHOR, P. 1993. Random debaters and the hardness of approximating stochastic functions. In Proceedings of the 9th Structure in Complexity Theory Conference. pp. 280-293.

[26]

CONDON, A., AND LADNER, R. 1989. On the complexity of space bounded interactive proofs. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 462-467.

[27]

COOK, S. A. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (Shaker Heights, Oh., May 3-5). ACM, New York, pp. 151-158.

[28]

FAGIN, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computer Computations, Richard Karp, ed. AMS, Providence, R.I., pp. 43-73.

[29]

FEIGE, U., GOLDWASSER, S., LOVASZ, L., SAFRA, S., AND SZEGEDY, M. 1991. Approximating clique is almost NP-complete. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 2-12.

[30]

FEIGE, U., AND LOVASZ, L. 1992. Two-prover one-round proof systems: Their power and their problems. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 733-741.

[31]

FORTNOW, L., ROMPEL, J., AND SIPSER, M. 1988. On the power of multi-prover interactive protocols. In Proceedings of the 3rd Conference on Structure in Complexity Theory. pp. 156-161.

[32]

FORTNOW, L., AND SIPSER, M. 1988. Are there interactive protocols for co-np languages? Inf. Proc. Lett. 28, 249-251.

[33]

GOLDWASSER, S., MICALI, S., AND RACKOFF, C. 1989. The knowledge complexity of interactive proofs. SIAM J. Comput. 18, 186-208.

[34]

HASTAD, J. 1996. Clique is hard to approximate within n#-#. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 627-636.

[35]

HASTAD, J. 1997. Some optimal inapproximability results. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 1-10.

[36]

KARP, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, Miller and Thatcher, eds. Plenum Press, New York, pp. 85-103.

[37]

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, ISTCS. IEEE Computer Society Press, New York, pp. 250-260.

[38]

KIWI, M., LUND, C., RUSSELL, A., SPIELMAN, D., AND SUNDARAM, R. 1994. Alternation in interaction. In Proceedings of the 9th Structure in Complexity Theory Conference. IEEE Computer Press, New York, pp. 294-303.

[39]

LAPIDOT, D., AND SHAMIR, A. 1991. Fully parallelized multi prover protocols for NEXPTIME. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 13-18.

[40]

LEVIN, L. 1973. Universal'nyie pereborny#e zadachi (universal search problems: in Russian). Prob. Per. Inf. 9, 3, 265-266.

[41]

LIPTON, R. 1989. Efficient checking of computations. In Proceedings of 6th STACS.

[42]

LUND, C., FORTNOW, L., KARLOFF, H., AND NISAN, N. 1992. Algebraic methods for interactive proof systems. J. ACM, 39, 4 (Oct.), 859-868.

[43]

LUND, C., AND YANNAKAKIS, M. 1994. On the hardness of approximating minimization problems. J. ACM, 41, 5 (Sept.), 960-981.

[44]

NAOR, J., AND NAOR, M. 1993. Small-bias probability spaces: efficient constructions and applications. Siam J. Comput., 22, 838-856.

[45]

PAPADIMITRIOU, C. 1994. Computational Complexity. Addison Wesley, Reading, Mass.

[46]

PAPADIMITRIOU, C., AND YANNAKAKIS, M. 1991. Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43, 425-440.

[47]

PHILLIPS, S., AND SAFRA, S. 1992. PCP and tighter bounds for approximating MAX-SNP. Manuscript.

[48]

PoI#ISI4CI4UK, A., AND SPIELMAN, D. 1994. Nearly-linear size holographic proofs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25), ACM, New York, pp. 194-203.

[49]

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 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 475-484.

[50]

RUBINFELD, R., AND SUDAN, M. 1992. Self-testing polynomial functions efficiently and over rational domains. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla., Jan. 27-29). ACM, New York, pp. 23-32.

[51]

SuaMIa, A. 1992. IP = PSPACE. J. ACM, 39, 4 (Oct.), 869-877.

[52]

SI4EN, A. 1991. Multilinearity test made easy. Manuscript.

[53]

UDAN, M. 1992. Efficient checking of polynomials and proofs and the hardness of approximation problems. Ph.D. dissertation. U.C. Berkeley, Berkeley, Calif.

[54]

ZUCKERMAN, D. 1991. Simulating BPP using a general weak random source. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 79-89.

[55]

ZUCKERMAN, D. 1993. NP-complete problems have a version that's hard to approximate. In Proceedings of the 8th Structure in Complexity Theory Conference, pp. 305-312.

Cited By

Barto LButti SKazda AViola CŽivný SSobocinski PLago UEsparza J(2024)Algebraic Approach to ApproximationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662076(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662076
Banakh DKozik MSobocinski PLago UEsparza J(2024)Injective hardness condition for PCSPsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662072(1-10)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662072
Dalmau VOpršal JSobocinski PLago UEsparza J(2024)Local consistency as a reduction between constraint satisfaction problemsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662068(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662068
Show More Cited By

Index Terms

Probabilistic checking of proofs: a new characterization of NP
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation

Recommendations

Hardness of Approximate Hypergraph Coloring

We introduce the notion of covering complexity of a verifier for probabilistically checkable proofs (PCPs). Such a verifier is given an input, a claimed theorem, and an oracle, representing a purported proof of the theorem. The verifier is also given a ...
A Completeness Theory for Polynomial (Turing) Kernelization

The framework of Bodlaender et al. (J Comput Sys Sci 75(8):423---434, 2009 ) and Fortnow and Santhanam (J Comput Sys Sci 77(1):91---106, 2011 ) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-...
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational Complexity

The 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

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 45, Issue 1

Jan. 1998

214 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/273865

Issue’s Table of Contents

Copyright © 1998 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1998

Published in JACM Volume 45, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

752
Total Citations
View Citations
3,287
Total Downloads

Downloads (Last 12 months)491
Downloads (Last 6 weeks)119

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Barto LButti SKazda AViola CŽivný SSobocinski PLago UEsparza J(2024)Algebraic Approach to ApproximationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662076(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662076
Banakh DKozik MSobocinski PLago UEsparza J(2024)Injective hardness condition for PCSPsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662072(1-10)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662072
Dalmau VOpršal JSobocinski PLago UEsparza J(2024)Local consistency as a reduction between constraint satisfaction problemsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662068(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662068
Ron-Zewi NRothblum R(2024)Local Proofs Approaching the Witness LengthJournal of the ACM10.1145/366148371:3(1-42)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3661483
Gharibian S(2024)Guest Column: The 7 faces of quantum NPACM SIGACT News10.1145/3639528.363953554:4(54-91)Online publication date: 3-Jan-2024
https://dl.acm.org/doi/10.1145/3639528.3639535
Guruswami VLin BRen XSun YWu KMohar BShinkar IO'Donnell R(2024)Parameterized Inapproximability Hypothesis under Exponential Time HypothesisProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649771(24-35)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649771
Hirahara SOhsaka NMohar BShinkar IO'Donnell R(2024)Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration ProblemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649667(1435-1445)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649667
Kothari PManohar PMohar BShinkar IO'Donnell R(2024)An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649640(776-787)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649640
Bhangale AHarsha PParadise OTal A(2024)Rigid Matrices from Rectangular PCPsSIAM Journal on Computing10.1137/22M149559753:2(480-523)Online publication date: 3-Apr-2024
https://doi.org/10.1137/22M1495597
Wang RHazay CVenkitasubramaniam M(2024)Ligetron: Lightweight Scalable End-to-End Zero-Knowledge Proofs Post-Quantum ZK-SNARKs on a Browser2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00086(1760-1776)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00086
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents