PCP characterizations of NP: toward a polynomially-small error-probability. (English) Zbl 1234.68133
Summary: 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 ^{\beta } n\), for any constant \(\beta < 1\), where \(n\) is the length of the proof. The BGLR conjecture asserts the same for any constant \(\beta \), for \(\beta \) 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.
We show that the number of bits that are read in each access to the proof can be made as high as \(\log ^{\beta } n\), for any constant \(\beta < 1\), where \(n\) is the length of the proof. The BGLR conjecture asserts the same for any constant \(\beta \), for \(\beta \) 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.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
References:
| [1] | M. Alekhnovich, S. Buss, S. Moran & T. Pitassi (1998). Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. Manuscript. · Zbl 0911.03028 |
| [2] | 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. · Zbl 1065.68570 |
| [3] | 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/ . · Zbl 0903.68076 |
| [4] | 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. · Zbl 0968.68145 |
| [5] | Babai L., Fortnow L., Lund C. (1991) Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1: 3–40 · Zbl 0774.68041 · doi:10.1007/BF01200056 |
| [6] | 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. |
| [7] | 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. · Zbl 1234.68133 |
| [8] | I. Dinur & S. Safra (1998). Monotone-Minimum-Satisfying Assignment is NP-hard for Almost Polynomial Factors. Manuscript. |
| [9] | Hastad J., Phillips R., Safra S. (1993) A well-characterized approximation problem. Information Processing Letters 47: 301–305 · Zbl 0782.68057 · doi:10.1016/0020-0190(93)90076-L |
| [10] | Carsten Lund , Mihalis Yannakakis (1994) On the Hardness of Approximating Minimization Problems. Journal of the ACM 41(5): 960–981 · Zbl 0814.68064 · doi:10.1145/185675.306789 |
| [11] | 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. · Zbl 0963.68175 |
| [12] | Ran Raz (1998) A Parallel Repetition Theorem. SIAM Journal on Computing 27(3): 763–803 · Zbl 0911.68082 · doi:10.1137/S0097539795280895 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
