首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:Resolution complexity of perfect mathcing principles for sparse graphs
  • 本地全文:下载
  • 作者:Dmitry Itsykson ; Mikhail Slabodkin ; Dmitry Sokolov
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], 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 matches with the upper bound 2 O ( n ) up to an application of a polynomial. Our result implies the 2 ( n ) lower bounds for the complete graph K n and the complete bipartite graph K n O ( n ) that improve the lower bounds followed from [Raz04]. Our results also implies 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.

  • 关键词:expander ; matching ; Resolution ; width
国家哲学社会科学文献中心版权所有