Infeasibility of instance compression and succinct PCPs for NP

ABSTRACT

The OR-SAT problem asks, given Boolean formulae Φ₁,...,Φ_m each of size at most n, whether at least one of the Φ_i's is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n, unless NP ⊆ coNP/poly, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et. al. [4] and Harnik and Naor [15] and has a number of implications. A number of parametric $\NP$ problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless NP ⊆ coNP/poly. Satisfiability does not have PCPs of size polynomial in the number of variables unless NP ⊆ coNP/poly. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form. (Buhrman-Hitchcock) There are no subexponential-size hard sets for NP unless NP is in co-NP/poly. We also study probabilistic variants of compression, and show various results about and connections between these variants. To this end, we introduce a new strong derandomization hypothesis, the Oracle Derandomization Hypothesis, and discuss how it relates to traditional derandomization assumptions.

REFERENCES

• 1: Leonard Adleman, Two theorems on random polynomial time, Proceedings of the 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), p.75-83, October 16-18, 1978
• 2: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 3: 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]
• 4: H. Bodlaender, R. Downey, M. Fellows, and D. Hermelin. On problems without polynomial kernels. Manuscript, 2007.
• 5: Harry Buhrman , John M. Hitchcock, NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.1-7, June 22-26, 2008 [doi>10.1109/CCC.2008.21]
• 6: Jin-Yi Cai , Venkatesan T. Chakaravarthy , Lane A. Hemaspaandra , Mitsunori Ogihara, Competing provers yield improved Karp-Lipton collapse results, Information and Computation, v.198 n.1, p.1-23, April 10, 2005 [doi>10.1016/j.ic.2005.01.002]
• 7: L. Cai, J. Chen, R. Downey, and M. Fellows. Advice classes of parameterized tractability. Annals of Pure and Applied logic, 84(1):119--138, 1997.
• 8: 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]
• 9: Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), v.54 n.3, p.12-es, June 2007 [doi>10.1145/1236457.1236459]
• 10: R. Downey and M. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
• 11: Bella Dubrov , Yuval Ishai, On the randomness complexity of efficient sampling, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132615]
• 12: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 13: L. Fortnow and R. Santhanam. Infeasibility of instance compression and succinct PCPs for NP. Electronic Colloquium on Computational Complexity (ECCC), 14(96), 2007.
• 14: Jiong Guo , Rolf Niedermeier, Invitation to data reduction and problem kernelization, ACM SIGACT News, v.38 n.1, March 2007 [doi>10.1145/1233481.1233493]
• 15: Danny Harnik , Moni Naor, On the Compressibility of NP Instances and Cryptographic Applications, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.719-728, October 21-24, 2006 [doi>10.1109/FOCS.2006.54]
• 16: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 17: Y. T. Kalai and R. Raz. Interactive PCP. Electronic Colloquium on Computational Complexity, 7(31), 2007.
• 18: R. Karp and R. Lipton. Turing machines that take advice. L’Enseignement Mathématique, 28(2):191--209, 1982.
• 19: Adam R. Klivans , Dieter van Melkebeek, Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses, SIAM Journal on Computing, v.31 n.5, p.1501-1526, 2002 [doi>10.1137/S0097539700389652]
• 20: S. Mahaney. Sparse complete sets for NP: Solution of a conjecture of berman and hartmanis. Journal of Computer and System Sciences, 25(2):130--143, 1982.
• 21: R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
• 22: C. Umans, Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.648, October 14-17, 2001
• 23: D. Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? Advances in Cryptology, EUROCRYPT 1998, Lecture Notes in Computer Science, 1403:334--345, 1998.
• 24: C.-K. Yap. Some consequences of non-uniform conditions on uniform classes. Theoretical Computer Science, 26:287--300, 1983.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

General Terms:
Algorithms, Security, Theory

Keywords:
cryptography, instance compression, parameterized complexity, polynomial hierarchy, succinct PCPs