Abstract
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given input in an NP language. In this paper, this is achieved by making a constant number of accesses to the proof, obtaining error probability that is exponentially small in the total number of bits that are read.
We show that the number of bits that are read in each access to the proof can be made as high as logβ n , for any constant β < 1, where n is the length of the proof. The BGLR conjecture asserts the same for any constant β, for β smaller or equal to 1.
Our results are in fact stronger, implying that the Gap-Quadratic-Solvability problem with a constant number of variables in each equation is NP-hard. That is, given a system of n quadratic equations over a field \({\mathcal{F}}\) of size up to \(2^{\log^\beta n}\), where each equation depends on a constant number of variables, it is NP-hard to distinguish between the case where there is a common solution to all of the equations and the case where any assignment satisfies at most a \({2 / |\mathcal{F}|}\) fraction of them.
At the same time, our proof presents a direct construction of a low-degree test whose error-probability is exponentially small in the number of bits accessed. Such a result was previously known only relying on recursive applications of the entire PCP theorem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Alekhnovich, S. Buss, S. Moran & T. Pitassi (1998). Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. Manuscript.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan & Mario Szegedy (1998). Proof verification and the hardness of approximation problems. Journal of the ACM 45(3), 501–555. ISSN 0004-5411.
Sanjeev Arora & Shmuel Safra (1998). Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM 45(1), 70–122. ISSN 0004-5411. http://www.acm.org:80/pubs/citations/journals/jacm/1998-45-1/p70-arora/.
Sanjeev Arora & Madhu Sudan (1997). Improved Low Degree Testing and its Applications. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 485–495. El Paso, Texas.
Babai L., Fortnow L., Lund C. (1991) Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1: 3–40
M. Bellare, S. Goldwasser, C. Lund & A. Russell (1993). Efficient Multi-Prover Interactive Proofs with Applications to Approximation Problems. In Proc. 25th ACM Symp. on Theory of Computing, 113–131.
I. Dinur, E. Fischer, G. Kindler, R. Raz & S. Safra (1999). PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. In Proc. 31th ACM Symp. on Theory of Computing.
I. Dinur & S. Safra (1998). Monotone-Minimum-Satisfying Assignment is NP-hard for Almost Polynomial Factors. Manuscript.
Hastad J., Phillips R., Safra S. (1993) A well-characterized approximation problem. Information Processing Letters 47: 301–305
Carsten Lund , Mihalis Yannakakis (1994) On the Hardness of Approximating Minimization Problems. Journal of the ACM 41(5): 960–981
R. Raz & S. Safra (1997). A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. In Proc. 29th ACM Symp. on Theory of Computing, 475–484.
Ran Raz (1998) A Parallel Repetition Theorem. SIAM Journal on Computing 27(3): 763–803
Acknowledgments
We wish to thank the anonymous referee for the careful reading of this manuscript and for many helpful comments.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Dinur, I., Fischer, E., Kindler, G. et al. PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. comput. complex. 20, 413–504 (2011). https://doi.org/10.1007/s00037-011-0014-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-011-0014-4