Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles. / Itsykson, Dmitry; Oparin, Vsevolod; Slabodkin, Mikhail; Sokolov, Dmitry.
в: Fundamenta Informaticae, Том 145, № 3, 01.01.2016, стр. 229-242.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles
AU - Itsykson, Dmitry
AU - Oparin, Vsevolod
AU - Slabodkin, Mikhail
AU - Sokolov, Dmitry
PY - 2016/1/1
Y1 - 2016/1/1
N2 - The resolution complexity of the perfect matching 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 Gn such that the resolution complexity of the perfect matching principle for Gn is 2Ω(n) where n is the number of vertices in Gn. This lower bound is tight up to some polynomial. Our result implies the 2Ω(n) lower bounds for the complete graph K2n + 1 and the complete bipartite graph Kn,O(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(n22n). Thus our lower bounds match 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].
AB - The resolution complexity of the perfect matching 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 Gn such that the resolution complexity of the perfect matching principle for Gn is 2Ω(n) where n is the number of vertices in Gn. This lower bound is tight up to some polynomial. Our result implies the 2Ω(n) lower bounds for the complete graph K2n + 1 and the complete bipartite graph Kn,O(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(n22n). Thus our lower bounds match 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].
KW - expander
KW - perfect matching
KW - proof complexity
KW - resolution
KW - width
UR - http://www.scopus.com/inward/record.url?scp=84984917469&partnerID=8YFLogxK
U2 - 10.3233/FI-2016-1358
DO - 10.3233/FI-2016-1358
M3 - Article
AN - SCOPUS:84984917469
VL - 145
SP - 229
EP - 242
JO - Fundamenta Informaticae
JF - Fundamenta Informaticae
SN - 0169-2968
IS - 3
ER -
ID: 49785629