Exponential lower bound for static semi-algebraic proofs

• Main Authors: Grigoriev, Dima., Hirsch, Edward A., Pasechnik, Dmitrii V.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2014
• Subjects: DRNTU::Science::Mathematics::Algebra
• Online Access: https://hdl.handle.net/10356/101864; http://hdl.handle.net/10220/18806
• Institution: Nanyang Technological University

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]....