Exponential lower bound for static semi-algebraic proofs
Semi-algebraic proof systems were introduced in [1] as extensions of Lovász-Schrijver proof systems [2,3]. These systems are very strong; in particular, they have short proofs of Tseitin’s tautologies, the pigeonhole principle, the symmetric knapsack problem and the clique-coloring tautologies [1]....
Saved in:
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2014
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/101864 http://hdl.handle.net/10220/18806 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | Semi-algebraic proof systems were introduced in [1] as extensions of Lovász-Schrijver proof systems [2,3]. These systems are very strong; in particular, they have short proofs of Tseitin’s tautologies, the pigeonhole principle, the symmetric knapsack problem and the clique-coloring tautologies [1].
In this paper we study static versions of these systems. We prove an exponential lower bound on the length of proofs in one such system. The same bound for two tree-like (dynamic) systems follows. The proof is based on a lower bound on the “Boolean degree” of Positivstellensatz Calculus refutations of the symmetric knapsack problem. |
|---|