Complexity of semi-algebraic proofs

Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

24 Цитирования (Scopus)

Аннотация

Proof systems for polynomial inequalities in 0-1 variables include the well-studied Cutting Planes proof system (CP) and the Lov´asz-Schrijver calculi (LS) utilizing linear, respectively, quadratic, inequalities. We introduce generalizations LSd of LSinvolving 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´asz-Schrijver ranks, demonstrating, in particular, their rather limited applicability for proof complexity.

Язык оригиналаанглийский
Название основной публикацииSTACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
РедакторыAfonso Ferreira, Helmut Alt
ИздательSpringer Nature
Страницы419-430
Число страниц12
ISBN (электронное издание)9783540432838
СостояниеОпубликовано - 1 янв 2002
Событие19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002 - Antibes - Juan les Pins, Франция
Продолжительность: 14 мар 200216 мар 2002

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том2285
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002
СтранаФранция
ГородAntibes - Juan les Pins
Период14/03/0216/03/02

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Complexity of semi-algebraic proofs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Grigoriev, D., Hirsch, E. A., & Pasechnik, D. V. (2002). Complexity of semi-algebraic proofs. В A. Ferreira, & H. Alt (Ред.), STACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (стр. 419-430). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 2285). Springer Nature.