The complexity of the Hajos calculus
The complexity of the Hajos calculus
复制标题
Hajos 演算的复杂性
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
A. Urquhart
中科院分区：
文献类型：
--
作者：
T. Pitassi;A. Urquhart
Hajos 构造是一个简单的、不确定的过程，用于生成不可 3 色的图类。 A.J.曼斯菲尔德和 D.J.A.威尔士人提出了证明对于每个非 3 色图是否存在多项式大小的 Hajos 构造的问题。本文的主要结果是证明 Hajos 演算是多项式有界的当且仅当扩展弗雷格证明系统是多项式有界的。这一结果将图论中的一个开放问题与命题证明系统复杂性中的一个重要开放问题联系起来。此外，作者还为 Hajos 演算的强子系统建立了指数下界。最后，他们讨论了这个结果的一个有趣的图论结果。<<ETX>>
The Hajos construction is a simple, nondeterministic procedure for generating the class of graphs that are not 3-colorable. A.J. Mansfield and D.J.A. Welsh have posed the problem of proving whether or not there exists a polynomial-size Hajos construction for every non-3-colorable graph. The main result of this paper is a proof that the Hajos calculus is polynomially-bounded if and only if extended Frege proof systems are polynomially bounded. This result links an open problem in graph theory to an important open problem in the complexity of propositional proof systems. In addition, the authors establish an exponential lower bound for a strong subsystem of the Hajos calculus. Lastly, they discuss an interesting graph-theoretical consequence of this result.<<ETX>>