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]....
| मुख्य लेखकों: | , , |
|---|---|
| अन्य लेखक: | |
| स्वरूप: | Journal Article |
| भाषा: | English |
| प्रकाशित: |
2014
|
| विषय: | |
| ऑनलाइन पहुंच: | https://hdl.handle.net/10356/101864 http://hdl.handle.net/10220/18806 |
| _version_ | 1826123605747957760 |
|---|---|
| author | Grigoriev, Dima. Hirsch, Edward A. Pasechnik, Dmitrii V. |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Grigoriev, Dima. Hirsch, Edward A. Pasechnik, Dmitrii V. |
| author_sort | Grigoriev, Dima. |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T06:07:24Z |
| format | Journal Article |
| id | ntu-10356/101864 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:07:24Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | ntu-10356/1018642023-02-28T19:43:22Z Exponential lower bound for static semi-algebraic proofs Grigoriev, Dima. Hirsch, Edward A. Pasechnik, Dmitrii V. School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Algebra 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. Accepted version 2014-02-17T07:17:40Z 2019-12-06T20:45:58Z 2014-02-17T07:17:40Z 2019-12-06T20:45:58Z 2002 2002 Journal Article Grigoriev, D., Hirsch, E. A., & Pasechnik, D. V. (2002). Exponential Lower Bound for Static Semi-algebraic Proofs. Automata, Languages and Programming, 2380, 257-268. https://hdl.handle.net/10356/101864 http://hdl.handle.net/10220/18806 10.1007/3-540-45465-9_23 en Automata, languages and programming © 2002 Springer. This is the author created version of a work that has been peer reviewed and accepted for publication by Automata, Languages and Programming, Springer. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [DOI:https://dx.doi.org/10.1007/3-540-45465-9_23]. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics::Algebra Grigoriev, Dima. Hirsch, Edward A. Pasechnik, Dmitrii V. Exponential lower bound for static semi-algebraic proofs |
| title | Exponential lower bound for static semi-algebraic proofs |
| title_full | Exponential lower bound for static semi-algebraic proofs |
| title_fullStr | Exponential lower bound for static semi-algebraic proofs |
| title_full_unstemmed | Exponential lower bound for static semi-algebraic proofs |
| title_short | Exponential lower bound for static semi-algebraic proofs |
| title_sort | exponential lower bound for static semi algebraic proofs |
| topic | DRNTU::Science::Mathematics::Algebra |
| url | https://hdl.handle.net/10356/101864 http://hdl.handle.net/10220/18806 |
| work_keys_str_mv | AT grigorievdima exponentiallowerboundforstaticsemialgebraicproofs AT hirschedwarda exponentiallowerboundforstaticsemialgebraicproofs AT pasechnikdmitriiv exponentiallowerboundforstaticsemialgebraicproofs |