Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-24T23:35:34.319Z Has data issue: false hasContentIssue false
  • English
  • Français

Structured pigeonhole principle, search problems and hard tautologies

Published online by Cambridge University Press:  12 March 2014

Jan Krajíček
Jan Krajíček*
Affiliation:
Mathematical Institute, Academy of Sciences, ŽitnÁ 25, Prague 1, CZ - 115 67 The Czech Republic, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider exponentially large finite relational structures (with the universe {0, 1}n ) whose basic relations are computed by polynomial size (n O(1)) circuits. We study behaviour of such structures when pulled back by P/poly maps to a bigger or to a smaller universe. In particular, we prove that:

1. If there exists a P/poly map g: {0, 1}n → {0, 1}m , n < m, iterable for a proof system then a tautology (independent of g) expressing that a particular size n set is dominating in a size 2n tournament is hard for the proof system.

2. The search problem WPHP. decoding RSA or finding a collision in a hashing function can be reduced to finding a size m homogeneous subgraph in a size 22m graph.

Further we reduce the proof complexity of a concrete tautology (expressing a Ramsey property of a graph) in strong systems to the complexity of implicit proofs of implicit formulas in weak proof systems.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 70 , Issue 2 , June 2005 , pp. 619 - 630
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Alekhnovich, M., Bkn-Sasson, E., Razborov, A. A., and Wigderson, A., Pseudorandom generators in propositional proof complexity, Electronic Colloquium on Computational Complexity, vol. 23 (2000), Extended abstract in: Proceedings of the 41st Annual Symposium on Foundation of Computer Science. (2000). pp. 43-53.Google Scholar
[2] Beame, P., Cook, S. A., Edmonds, J., Impagliazzo, R., and Pitassi, T., The relative complexity of NP search problems, Proceedings 27th Annual ACM Symposium on the Theory of Computing, 1995, pp. 303–314.Google Scholar
[3] Chiari, M. and KraÍČek, J., Witnessing functions in hounded arithmetic and search problems, this Journal, vol. 63 (1998), no. 3, pp. 1095–1115.Google Scholar
[4] Chiari, M., Lifting independence results in bounded arithmetic, Archive for Mathematical Logic, vol. 38 (1999), no. 2, pp. 123–138.CrossRefGoogle Scholar
[5] Cook, S. A., Feasibly constructive proofs and the propositional calculus, Proceedings 7th Annual ACM Symposium on Theory of Computing, ACM Press, 1975, pp. 83–97.Google Scholar
[6] Cook, S. A. and Reckhow, A. R., The relative efficiency of propositional proof systems, this Journal, vol. 44 (1979), no. 1, pp. 36–50.Google Scholar
[7] ErdÖs, P., Some remarks on the theory of graphs, Bulletin of the AMS, vol. 53 (1947), pp. 292–294.CrossRefGoogle Scholar
[8] Hanika, J., Herhrandizing search problems in bounded arithmetic, Mathematical Logic Quarterly, vol. 50 (2004), no. 6, pp. 577–586.CrossRefGoogle Scholar
[9] Hanika, J., Search problems and bounded arithmetic, Ph.D. thesis, Charles University, 2004.CrossRefGoogle Scholar
[10] KrajÍČek, J., Bounded arithmetic, propositional logic, and complexity theory, Encyclopedia of mathematics and its applications, vol. 60, Cambridge University Press, 1995.Google Scholar
[11] KrajÍČek, J., On the weak pigeonhole principle, Fundamenta Mathematicae, vol. 170 (2001), no. 1-3, pp. 123–140.CrossRefGoogle Scholar
[12] KrajÍČek, J., Tautologies from pseudo-random generators, The Bulletin of Symbolic Logic, vol. 7 (2001), no. 2, pp. 197–212.CrossRefGoogle Scholar
[13] KrajÍČek, J., Diagonalization in proof complexity, Fundamenta Mathematicae, vol. 182 (2004), pp. 181–192.CrossRefGoogle Scholar
[14] KrajÍČek, J., Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds, this Journal, vol. 69 (2004), no. 1, pp. 265–286.Google Scholar
[15] KrajÍČek, J., Implicit proofs, this Journal, vol. 69 (2004), no. 2, pp. 387–397.Google Scholar
[16] KrajÍČek, J. and PudlÁk, P., Propositional proof systems, the consistency of first order theories and the complexity of computations, this Journal, vol. 54 (1989), no. 3, pp. 1063–1079.Google Scholar
[17] KrajÍČek, J., Some consequences of cryptographical conjectures for S2 1 and EF, Information and Computation, vol. 140 (1998), no. 1, pp. 82–94.CrossRefGoogle Scholar
[18] Maciel, A., Pitassi, T., and Woods, A., A new proof of the weak pigeonhole principle, Journal of Computer and Systems Science, vol. 64 (2002), pp. 843–872.CrossRefGoogle Scholar
[19] Paris, J. B., Wilkie, A. J., and Woods, A., Provability of the pigeonhole principle and the existence of infinitely many primes, this Journal, vol. 53 (1988), pp. 1235–1244.Google Scholar
[20] Raz, R., Resolution lower bounds for the weak pigeonhole principle, Proceedings of the 34th STOC, 2002, pp. 553–562.Google Scholar
[21] Razborov, A. A., Formulas of bounded depth in the basis (&,⊕) andsome combinatorial problems, Voprosy Kibemetiki, vol. 134 (1988), pp. 149–166, (in Russian).Google Scholar
[22] Razborov, A. A., Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic, Rossiĭskaya Akademiya Nauk. Izvestiya. Seriya Matematicheskaya. vol. 59 (1995), no. 1, pp. 201–224.Google Scholar
[23] Razborov, A. A., Resolution lower bounds for perfect matching principles, Proceedings of the 17th IEEE conference on computational complexity, 2002, pp. 29–38.Google Scholar
[24] Razborov, A. A., Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution, preprint, May 2003.Google Scholar
[25] Stinson, D. R., Cryptography: theory and practice, CRC Press LLC, 1995.Google Scholar