Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles

• Autorzy: Itsykson D. , Slabodkin M. , Oparin V. , Sokolov D.

Identyfikatory

DOI

10.3233/FI-2016-1358

• Języki publikacji: EN

Abstrakty

EN

The resolution complexity of the perfectmatching principle was studied by Razborov [1], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph G_n such that the resolution complexity of the perfect matching principle for G_n is 2^Ω(n)) where n is the number of vertices in G_n. This lower bound is tight up to some polynomial. Our result implies the 2^Ω(n) lower bounds for the complete graph K_2n+1 and the complete bipartite graph K_nO(n), that improves the lower bounds following from [1]. We show that for every graph G with n vertices that has no perfect matching there exists a resolution refutation of perfect matching principle for G of size O(n²2ⁿ). Thus our lower boundsmatch upper bounds up to a multiplicative constant in the exponent. Our results also imply the well-known exponential lower bounds on the resolution complexity of the pigeonhole principle, the functional pigeonhole principle and the pigeonhole principle over a graph. We also prove the following corollary. For every natural number d, for every n large enough, for every function h : {1, 2, . . . , n} → {1, 2, . . . , d}, we construct a graph with n vertices that has the following properties. There exists a constant D such that the degree of the i-th vertex is at least h(i) and at most D, and it is impossible to make all degrees equal to h(i) by removing the graph's edges. Moreover, any proof of this statement in the resolution proof system has size 2^Ω(n). This result implies well-known exponential lower bounds on the Tseitin formulas as well as new results: for example, the same property of a complete graph. Preliminary version of this paper appeared in proceedings of CSR-2015 [2].

Słowa kluczowe

EN

expander; perfect matching; proof complexity; resolution; width

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 229--242
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Itsykson D.

• Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St.Petersburg, 191023, Russia

autor

Slabodkin M.

• St. Petersburg Academic University, 8 Khlopina, St.Petersburg, 194021, Russia

autor

Oparin V.

• St. Petersburg Academic University, 8 Khlopina, St.Petersburg, 194021, Russia

autor

Sokolov D.

• Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St.Petersburg, 191023, Russia

Bibliografia

• [1] Razborov AA. Resolution lower bounds for perfect matching principles. Journal of Computer and System Sciences. 2004;69(1):3–27.
• [2] Itsykson D, Slabodkin M, Sokolov D. Resolution complexity of perfect matching principles for sparse graphs. In: Proceedings of CSR-2015. vol. 9139 of Lecture Notes in Computer Science; 2015. p. 219–230.
• [3] Haken A. The intractability of resolution. Theoretical Computer Science. 1985;39:297–308.
• [4] Raz R. Resolution Lower Bounds for the Weak Pigeonhole Principle. Electronic Colloquium on Computational Complexity; 2001. 01-021.
• [5] Razborov AA. Resolution Lower Bounds for the Weak Pigeonhole Principle. Electronic Colloquium on Computational Complexity; 2001. 01-055.
• [6] Urquhart A. Resolution Proofs of Matching Principles. Annals of Mathematics and Artificial Intelligence. 2003 Mar;37(3):241–250. doi:10.1023/A:1021231610627.
• [7] Ben-Sasson E, Wigderson A. Short proofs are narrow — resolution made simple. Journal of ACM. 2001;48(2):149–169.
• [8] Razborov AA. Resolution lower bounds for the weak functional pigeonhole principle. Theoretical Computer Science. 2003;303(1):233–243.
• [9] Alekhnovich M. Mutilated Chessboard Problem is Exponentially Hard for Resolution. Theor Comput Sci. 2004 Jan;310(1-3):513–525. doi:10.1016/S0304-3975(03)00395-5.
• [10] Dantchev SS, Riis S. ”Planar” Tautologies Hard for Resolution. In: FOCS; 2001. p. 220–229.
• [11] Buss S, Pitassi T. Resolution and the weak pigeonhole principle. In: Proceedings of the CSL97, Lecture Notes in Computer Science. vol. 1414; 1997. p. 149–156.
• [12] Itsykson D, Sokolov D. Lower bounds for myopic DPLL algorithms with a cut heuristic. In: Proceedings of the 22nd international conference on Algorithms and Computation. ISAAC’11. Berlin, Heidelberg: Springer-Verlag, available as ECCC Report TR12-141; 2011. p. 464–473. doi:10.1007/978-3-642-25591-5 48.
• [13] M Capalbo SV O Reingold, Wigderson A. Randomness conductors and constant-degree expansion beyond the degree/2 barrier. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing; 2002. p. 659–668.
• [14] Hoory S, Linial N, Wigderson A. Expander Graphs and Their Applications. Bulletin of the American Mathematical Society. 2006;43:439–561.
• [15] Urquhart A. Hard Examples for Resolution. JACM. 1987;34(1):209–219.
• [16] Alekhnovich M, Hirsch EA, Itsykson D. Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J Autom Reason. 2005;35(1-3):51–72.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).