Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
复制标题
Lovász-Schrijver 和 Sherali-Adams 证明系统的等级复杂度差距
DOI：
10.1007/s00037-012-0049-1
复制
发表时间：
2012
影响因子：
1.4
通讯作者：
Dantchev S
中科院分区：
文献类型：
--
作者：
Dantchev S
我们证明了一个二分法定理的命题矛盾的秩，统一产生的一阶句子，在两个Lovász-Schrijver（LS）和Sherali-Adams（SA）反驳系统。更确切地说，我们首先表明，命题翻译的一阶公式是普遍错误的，也就是说，失败的所有有限和无限的模型，有LS证明，其秩是常数，独立的（有限）宇宙的大小。与此相反，我们证明了在所有有限模型中失败，但在某些无限结构中成立的命题公式，需要证明其SA秩随宇宙的大小多项式增长。到目前为止，这种所谓的复杂性缺口定理已经被称为树型归结，并以某种限制形式，为归结和零星系统。据我们所知，这是第一次Sherali-Adams提升和投影方法被认为是一个命题反驳系统（自本文的会议版本以来，SA在其他几篇论文中被认为是一个反驳系统）。SA系统的一个有趣的特性是它以保秩的方式模拟LS，即没有半定割的Lovász-Schrijver反驳系统。
We prove a dichotomy theorem for the rank of propositional contradictions, uniformly generated from first-order sentences, in both the Lovász-Schrijver (LS) and Sherali-Adams (SA) refutation systems. More precisely, we first show that the propositional translations of first-order formulae that are universally false, that is, fail in all finite and infinite models, have LS proofs whose rank is constant, independent of the size of the (finite) universe. In contrast to that, we prove that the propositional formulae that fail in all finite models, but hold in some infinite structure, require proofs whose SA rank grows polynomially with the size of the universe.Until now, this kind of so-called complexity gap theorem has been known for tree-like Resolution and, in somehow restricted forms, for the Resolution and Nullstellensatz systems. As far as we are aware, this is the first time the Sherali-Adams lift-and-project method has been considered as a propositional refutation system (since the conference version of this paper, SA has been considered as a refutation system in several further papers). An interesting feature of the SA system is that it simulates LS, the Lovász-Schrijver refutation system without semi-definite cuts, in a rank-preserving fashion.
登录
查看更多内容
Lov[a-acute]sz 的下限 - Schrijver Systems 及其他系统遵循多方通信复杂性
DOI：
--
发表时间：
2007
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
P. Beame;T. Pitassi;Nathan Segerlind
通讯作者：
Nathan Segerlind
论命题微积分公式的复杂性
DOI：
--
发表时间：
2001
期刊：
Scientific Annals of Cuza University
影响因子：
--
作者：
S. Andrei;G. Grigoraș;M. Kudlek;Cristian Masalagiu
通讯作者：
Cristian Masalagiu
匹配多面体的 Sherali-adams 松弛
DOI：
--
发表时间：
2009
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Claire Mathieu;A. Sinclair
通讯作者：
A. Sinclair
DOI：
--
发表时间：
2008
期刊：
2008 23rd Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Søren Riis
通讯作者：
Søren Riis
树解析的复杂性差距
影响因子：
1.4
作者：
Søren Riis
通讯作者：
Søren Riis