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 cliquecoloring tautologies [1]. In this paper we study static versions of these systems.W e 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.

Язык оригиналаанглийский
Название основной публикацииAutomata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings
Страницы257-268
Число страниц12
СостояниеОпубликовано - 1 дек 2002
Событие29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 - Malaga, Испания
Продолжительность: 8 июл 200213 июл 2002

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

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

конференция

конференция29th International Colloquium on Automata, Languages, and Programming, ICALP 2002
Страна/TерриторияИспания
ГородMalaga
Период8/07/0213/07/02

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

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

ID: 49829085