Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-22T20:34:00.343Z Has data issue: false hasContentIssue false
  • English
  • Français

LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE

Published online by Cambridge University Press:  22 April 2015

ALBERT ATSERIAS ,
MORITZ MÜLLER  and
SERGI OLIVA
ALBERT ATSERIAS
Affiliation:
UNIVERSITAT POLITÈCNICA DE CATALUNYA BARCELONA, SPAIN
MORITZ MÜLLER
Affiliation:
KURT GÖDEL RESEARCH CENTER VIENNA, AUSTRIA
SERGI OLIVA
Affiliation:
UNIVERSITAT POLITÈCNICA DE CATALUNYA BARCELONA, SPAIN
Get access Rights & Permissions [Opens in a new window]

Abstract

The relativized weak pigeonhole principle states that if at least 2n out of n2 pigeons fly into n holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size $2^{\left( {{\rm{log\ }}n} \right)^{3/2 - \varepsilon } } $ for every ε﹥0 and every sufficiently large n. By reducing it to the standard weak pigeonhole principle with 2n pigeons and n holes, we also show that this lower bound is essentially tight in that there exist DNF-refutations of size $2^{\left( {{\rm{log\ }}n} \right)^{O\left( 1 \right)} } $ even in R(log). For the lower bound proof we need to discuss the existence of unbalanced low-degree bipartite expanders satisfying a certain robustness condition.

Keywords

Proof complexitybounded arithmeticweak pigeonhole principlesapproximate countingbounded-depth frege
Type
Articles
Information
The Journal of Symbolic Logic , Volume 80 , Issue 2 , June 2015 , pp. 450 - 476
Copyright
Copyright © The Association for Symbolic Logic 2015 

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

Ajtai, M., The complexity of the pigeonhole principle, Proceedings of the 29th Annual Symposium on the Foundations of Computer Science (FOCS ′88), IEEE Computer Society, White Plains, New York, pp. 346–355, 1988.Google Scholar
Ajtai, M., Approximate counting with uniform constant-depth circuits, Advances in computational complexity theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 1–20, 1993.Google Scholar
Ajtai, M. and Ben-Or, M., A theorem on probabilistic constant depth computations, Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC ′84), pp. 471–474, http://doi.acm.org/10.1145/800057.808715, ACM, New York, NY, 1984.Google Scholar
Atserias, A., Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms. Theoretical Computer Science, vol. 295 (2003), no. 1–3, pp. 27–39.Google Scholar
Atserias, A., On sufficient conditions for unsatisfiability of random formulas. Journal of the ACM, vol. 51 (2004), no. 2, pp. 281–311.Google Scholar
Atserias, A., Bonet, M.L., and Esteban, J.L., Lower bounds for the weak pigeonhole principle and random formulas beyond resolution. Information and Computation, vol. 176 (2002), no. 2, pp. 136–152.Google Scholar
Barrington, D. A. M., Immerman, N., and Straubing, H., On uniformity within NC. Journal of Computer and System Sciences, vol. 41 (1990), no. 3, pp. 274–306.Google Scholar
Beame, P., Impagliazzo, R., and Pitassi, T., Exponential lower bounds for the pigeonhole principle. Computational Complexity, vol. 3 (1993), no. 2, pp. 97–140.Google Scholar
Ben-Sasson, E. and Galesi, N., Space complexity of random formulae in resolution. Random Structures and Algorithms, vol. 23 (2003), no. 1, pp. 92–109.CrossRefGoogle Scholar
Ben-Sasson, E. and Wigderson, A., Short proofs are narrow – resolution made simple. Journal of the ACM, vol. 48 (2001), no. 2, pp. 149–169.CrossRefGoogle Scholar
Bollobás, B., Random Graphs, second edition, Cambridge University Press, Cambridge, UK, 2001.Google Scholar
Buss, S. R., Polynomial size proofs of the propositional pigeonhole principle, this Journal, vol. 52 (1987), no. 4, pp. 916–927.Google Scholar
Buss, S. R., First-Order Proof Theory of Arithmetic, Handbook of Proof Theory (Buss, S. R., editor), Elsevier, 1998, pp. 79–147.Google Scholar
Cook, S. A. and Reckhow, R. A., The relative efficiency of propositional proof systems, this Journal, vol. 44 (1979), no. 1, pp. 36–50.Google Scholar
Dantchev, S. and Riis, S., On relativisation and complexity gap for resolution-based proof systems, Proceedings of 17th Annual Conference of the European Association for Computer Science Logic (CSL), Lecture Notes in Computer Science, vol. 2803, pp. 142–154, Springer, Berlin, 2003.Google Scholar
Furst, M. L., Saxe, J. B., and Sipser, M., Parity, circuits, and the polynomial-time hierarchy, Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (FOCS ′81), pp. 260–270, IEEE Computer Society, Washington, DC, 1981.Google Scholar
Furst, M. L., Saxe, J. B., and Sipser, M., Parity, circuits, and the polynomial-time hierarchy. Theory of Computing Systems, vol. 17 (1984), no. 1, pp. 13–27.Google Scholar
Haken, A., The intractability of resolution, Theoretical Computer Science, vol. 39 (1985), no. 2–3, pp. 297–308.Google Scholar
Krajíček, J., Bounded Arithmetic, Propositional Logic, and Complexity Theory, Encyclopedia of Mathematics and its Applications, vol. 60, Cambridge University Press, New York, 1995.Google Scholar
Krajíček, J., On the weak pigeonhole principle. Fundamenta Mathematicae, vol. 170 (2001), no. 1–3, pp. 123–140.CrossRefGoogle Scholar
Krajíček, J., Combinatorics of first order structures and propositional proof systems. Archive for Mathematical Logic, vol. 43 (2004), no. 4, pp. 427–441.Google Scholar
Krajíček, J., Pudlák, P., and Woods, A., An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures & Algorithms, vol. 7 (1995), no. 1, pp. 15–39.Google Scholar
Maciel, A., Pitassi, T., and Woods, A. R., A new proof of the weak pigeonhole principle. Journal of Computer and System Sciences, vol. 64 (2002), no. 4, pp. 843–872.Google Scholar
Paris, J.B. and Wilkie, A.J., Counting problems in bounded arithmetic, Methods in Mathematical Logic, Lecture Notes in Mathematics, vol. 1130, pp. 317–340, 1985.CrossRefGoogle Scholar
Paris, J.B., Wilkie, A.J., and Woods, A.R., Provability of the pigeonhole principle and the existence of infinitely many primes, this Journal, vol. 53 (1988), no. 4, pp. 1235–1244.Google Scholar
Pudlák, P., A bottom-up approach to foundations of mathematics, Gödel′ (Hajek, P., editor,) Lecture Notes in Logic, vol. 6, pp. 81–97, Springer, 1996.Google Scholar
Pudlák, P., Proofs as games, American Mathematical Monthly, vol. 107, no. 6, pp. 541–550, 2000.Google Scholar
Raz, R., Resolution lower bounds for the weak pigeonhole principle. Journal of the ACM, vol. 51 (2004), no. 2, pp. 115–138.Google Scholar
Razborov, A. A., Resolution lower bounds for the weak functional pigeonhole principle. Theoretical Computer Science, vol. 1 (2003), no. 303, pp. 233–243.Google Scholar
Razborov, A. A., Pseudorandom generators hard for k-DNF resolution and polynomial calculus, Annals of Mathematics, vol. 181 (2015), no. 2, pp. 415–472.Google Scholar
Riis, S., A complexity gap for tree-resolution. Computational Complexity, vol. 10 (2001), pp. 179–209.Google Scholar
Robbins, H., A remark on Stirling’s formula. The American Mathematical Monthly, vol. 62 (1955), no. 1, pp. 26–29.Google Scholar
Segerlind, N., The complexity of propositional proofs. The Bulletin of Symbolic Logic, vol. 13 (2007), no. 4, pp. 417–481.CrossRefGoogle Scholar
Segerlind, N., Buss, S. R., and Impagliazzo, R., A switching lemma for small restrictions and lower bounds for k-DNF resolution. SIAM Journal on Computing, vol. 33 (2004), no. 5, pp. 1171–1200.Google Scholar
Stockmeyer, L. J., The Complexity of Approximate Counting (Preliminary Version), Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC ′83), ACM, New York, NY, pp. 118–126, 1983.Google Scholar
Viola, E., On approximate majority and probabilistic time. Computational Complexity, vol. 18 (2009), no. 3, pp. 337–375.Google Scholar
Viola, E., Randomness Buys Depth for Approximate Counting. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS ′11), IEEE Society Press, Palm Springs, CA, pp. 230–239, 2011.Google Scholar