Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 июл 2002 → 13 июл 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/02 → 13/07/02 |
ID: 49829085