Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
A major proof complexity problem is to prove a superpolynomial lower bound on the length of Frege proofs of arbitrary depth. A more general question is to prove an Extended Frege lower bound. Surprisingly, proving such bounds turns out to be much easier in the algebraic setting. In this paper, we study a proof system that can simulate Extended Frege: an extension of the Polynomial Calculus proof system where we can take a square root and introduce new variables that are equivalent to arbitrary depth algebraic circuits. We prove that an instance of the subset-sum principle, the binary value principle 1 + x1 + 2x2 +... + 2 n− 1xn = 0 (BVPn), requires refutations of exponential bit size over Q in this system. Part and Tzameret [18] proved an exponential lower bound on the size of Res-Lin (Resolution over linear equations [22]) refutations of BVPn. We show that our system p-simulates Res-Lin and thus we get an alternative exponential lower bound for the size of Res-Lin refutations of BVPn.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | 36th Computational Complexity Conference (CCC 2021) |
| Редакторы | Valentine Kabanets |
| Место публикации | Dagstuhl, Germany |
| Издатель | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Страницы | 21:1-21:18 |
| Число страниц | 18 |
| Том | 200 |
| ISBN (электронное издание) | 9783959771931 |
| ISBN (печатное издание) | 978-3-95977-193-1 |
| DOI | |
| Состояние | Опубликовано - 1 июл 2021 |
| Событие | 36th Computational Complexity Conference, CCC 2021 - Virtual, Toronto, Канада Продолжительность: 20 июл 2021 → 23 июл 2021 |
| Название | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Том | 200 |
| ISSN (печатное издание) | 1868-8969 |
| конференция | 36th Computational Complexity Conference, CCC 2021 |
|---|---|
| Страна/Tерритория | Канада |
| Город | Virtual, Toronto |
| Период | 20/07/21 → 23/07/21 |
ID: 84894589