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