Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles

摘要

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 G(n) such that the resolution complexity of the perfect matching principle for G(n) is 2(Omega(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(Omega(n)) lower bounds for the complete graph K2n+1 and the complete bipartite graph K-n,K- 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 (n(2)2(n)). 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.