Complexity of semi-algebraic proofs
Proof systems for polynomial inequalities in 0-1 variables include the well-studied Cutting Planes proof system (CP) and the Lovász- Schrijver calculi (LS) utilizing linear, respectively, quadratic, inequalities. We introduce generalizations LSd of LS involving polynomial inequalities of degree at m...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/95181 http://hdl.handle.net/10220/9273 |
| _version_ | 1811695286396911616 |
|---|---|
| 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 | Proof systems for polynomial inequalities in 0-1 variables include the well-studied Cutting Planes proof system (CP) and the Lovász- Schrijver calculi (LS) utilizing linear, respectively, quadratic, inequalities. We introduce generalizations LSd of LS involving polynomial inequalities of degree at most d.
Surprisingly, the systems LSd turn out to be very strong. We construct polynomial-size bounded degree LSd proofs of the clique-coloring tautologies (which have no polynomial-size CP proofs), the symmetric knapsack problem (which has no bounded degree Positivstellensatz Calculus (PC) proofs), and Tseitin’s tautologies (hard for many known proof systems). Extending our systems with a division rule yields a polynomial simulation of CP with polynomially bounded coefficients, while other extra rules further reduce the proof degrees for the aforementioned examples. Finally, we prove lower bounds on Lovász-Schrijver ranks, demonstrating, in particular, their rather limited applicability for proof complexity. |
| first_indexed | 2024-10-01T07:21:03Z |
| format | Journal Article |
| id | ntu-10356/95181 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:21:03Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/951812023-02-28T19:24:31Z Complexity of semi-algebraic proofs Grigoriev, Dima Hirsch, Edward A. Pasechnik, Dmitrii V. School of Physical and Mathematical Sciences Proof systems for polynomial inequalities in 0-1 variables include the well-studied Cutting Planes proof system (CP) and the Lovász- Schrijver calculi (LS) utilizing linear, respectively, quadratic, inequalities. We introduce generalizations LSd of LS involving polynomial inequalities of degree at most d. Surprisingly, the systems LSd turn out to be very strong. We construct polynomial-size bounded degree LSd proofs of the clique-coloring tautologies (which have no polynomial-size CP proofs), the symmetric knapsack problem (which has no bounded degree Positivstellensatz Calculus (PC) proofs), and Tseitin’s tautologies (hard for many known proof systems). Extending our systems with a division rule yields a polynomial simulation of CP with polynomially bounded coefficients, while other extra rules further reduce the proof degrees for the aforementioned examples. Finally, we prove lower bounds on Lovász-Schrijver ranks, demonstrating, in particular, their rather limited applicability for proof complexity. Accepted version 2013-02-27T03:50:03Z 2019-12-06T19:09:46Z 2013-02-27T03:50:03Z 2019-12-06T19:09:46Z 2002 2002 Journal Article Grigoriev, Dima., Hirsch, Edward A., & Pasechnik, Dmitrii V. (2002). Complexity of Semi-algebraic Proofs. Lecture Notes in Computer Science, 2285, 419-430. 0302-9743 https://hdl.handle.net/10356/95181 http://hdl.handle.net/10220/9273 10.1007/3-540-45841-7_34 en Lecture notes in computer science © 2002 Springer-Verlag Berlin Heidelberg. This is the author created version of a work that has been peer reviewed and accepted for publication by Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg. 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: [http://dx.doi.org/10.1007/3-540-45841-7_34]. application/pdf |
| spellingShingle | Grigoriev, Dima Hirsch, Edward A. Pasechnik, Dmitrii V. Complexity of semi-algebraic proofs |
| title | Complexity of semi-algebraic proofs |
| title_full | Complexity of semi-algebraic proofs |
| title_fullStr | Complexity of semi-algebraic proofs |
| title_full_unstemmed | Complexity of semi-algebraic proofs |
| title_short | Complexity of semi-algebraic proofs |
| title_sort | complexity of semi algebraic proofs |
| url | https://hdl.handle.net/10356/95181 http://hdl.handle.net/10220/9273 |
| work_keys_str_mv | AT grigorievdima complexityofsemialgebraicproofs AT hirschedwarda complexityofsemialgebraicproofs AT pasechnikdmitriiv complexityofsemialgebraicproofs |