Dantchev, Stefan and Martin, Barnaby and Rhodes, Mark (2009) 'Tight rank lower bounds for the Sherali–Adams proof system.', Theoretical computer science., 410 (21-23). pp. 2054-2063.
Abstract
We consider a proof (more accurately, refutation) system based on the Sherali–Adams (SA) operator associated with integer linear programming. If F is a CNF contradiction that admits a Resolution refutation of width k and size s, then we prove that the SA rank of F is ≤k and the SA size of F is ≤(k+1)s+1. We establish that the SA rank of both the Pigeonhole Principle and the Least Number Principle LNPn is n−2. Since the SA refutation system rank-simulates the refutation system of Lovász–Schrijver without semidefinite cuts (LS), we obtain as a corollary linear rank lower bounds for both of these principles in LS
| Item Type: | Article |
|---|---|
| Keywords: | Propositional proof complexity, Lift-and-project methods. |
| Full text: | Full text not available from this repository. |
| Publisher Web site: | https://doi.org/10.1016/j.tcs.2009.01.002 |
| Date accepted: | 03 January 2009 |
| Date deposited: | No date available |
| Date of first online publication: | 10 January 2009 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
