Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings
Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings
复制标题
数学理论与计算实践 - 第五届欧洲可计算性会议，CiE 2009，德国海德堡，2009 年 7 月 19-24 日。会议记录
DOI：
10.1007/978-3-642-03073-4_15
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Dantchev S
中科院分区：
文献类型：
--
作者：
Dantchev S
我们介绍了Gomory和Chvátal的切割平面（CP）系统的参数切割宽度。本文给出了两个简单多面体的截宽的线性下界。把CP看作一个命题反驳系统，可以看出CNF矛盾F的割宽总是由F的归结宽度上界。我们提供一个例子证明匡威失败：有一个F具有常数割宽，但具有分辨率宽度Ω（n）。按照一个标准的方法转换一个FO句子的F，没有有限的模型，到一个序列的CNFs，F，n，我们提供了一个分类定理CP的基础上的总和cutwidth加上秩。具体地说，F的截宽+秩是由一个常数约束的（仅取决于f）当且仅当f没有（无限的）模型。这个结果可以看作是文献中现存的各种间隙定理的一个相对结果。
We introduce the parameter cutwidth for the Cutting Planes (CP) system of Gomory and Chvátal. We provide linear lower bounds on cutwidth for two simple polytopes. ConsideringCPas a propositional refutation system, one can see that the cutwidth of a CNF contradictionFis always bound above by the Resolution width ofF. We provide an example proving that the converse fails: there is anFwhich has constant cutwidth, but has Resolution widthΩ(n). Following a standard method for converting an FO sentenceψ, without finite models, into a sequence of CNFs,Fψ,n, we provide a classification theorem forCPbased on the sum cutwidth plus rank. Specifically, the cutwidth + rank ofFψ,nis bound by a constantc(depending onψonly) iffψhas no (infinite) models. This result may be seen as a relative of various gap theorems extant in the literature.