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: | , , |
|---|---|
| 其他作者: | |
| 格式: | Article |
| 語言: | English |
| 出版: |
2014
|
| 主題: | |
| 在線閱讀: | https://hdl.handle.net/10356/101864 http://hdl.handle.net/10220/18806 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 機構: | Nanyang Technological University |
| 語言: | English |
| id |
sg-ntu-dr.10356-101864 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.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 |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
NTU Library |
| collection |
DR-NTU |
| language |
English |
| topic |
DRNTU::Science::Mathematics::Algebra |
| spellingShingle |
DRNTU::Science::Mathematics::Algebra Grigoriev, Dima. Hirsch, Edward A. Pasechnik, Dmitrii V. Exponential lower bound for static semi-algebraic proofs |
| 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. |
| author2 |
School of Physical and Mathematical Sciences |
| author_facet |
School of Physical and Mathematical Sciences Grigoriev, Dima. Hirsch, Edward A. Pasechnik, Dmitrii V. |
| format |
Article |
| author |
Grigoriev, Dima. Hirsch, Edward A. Pasechnik, Dmitrii V. |
| author_sort |
Grigoriev, Dima. |
| title |
Exponential lower bound for static semi-algebraic proofs |
| title_short |
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_sort |
exponential lower bound for static semi-algebraic proofs |
| publishDate |
2014 |
| url |
https://hdl.handle.net/10356/101864 http://hdl.handle.net/10220/18806 |
| _version_ |
1759856132367581184 |