Skip to main content

Research Repository

Advanced Search

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

Dantchev, Stefan; Martin, Barnaby

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems Thumbnail


Authors



Abstract

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.

Citation

Dantchev, S., & Martin, B. (2013). Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Computational Complexity, 22(1), 191-213. https://doi.org/10.1007/s00037-012-0049-1

Journal Article Type Article
Online Publication Date Nov 6, 2012
Publication Date Mar 1, 2013
Deposit Date Dec 19, 2011
Publicly Available Date Sep 27, 2017
Journal Computational Complexity
Print ISSN 1016-3328
Electronic ISSN 1420-8954
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 22
Issue 1
Pages 191-213
DOI https://doi.org/10.1007/s00037-012-0049-1

Files







You might also like



Downloadable Citations