A trade-off between length and width in resolution
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00462811" target="_blank" >RIV/67985840:_____/16:00462811 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.4086/toc.2016.v012a005" target="_blank" >http://dx.doi.org/10.4086/toc.2016.v012a005</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4086/toc.2016.v012a005" target="_blank" >10.4086/toc.2016.v012a005</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A trade-off between length and width in resolution
Popis výsledku v původním jazyce
We describe a family of CNF formulas in n variables, with small initial width, which have polynomial length resolution refutations. By a result of Ben-Sasson and Wigderson it follows that they must also have narrow resolution refutations, of width ... We show that, for our formulas, this decrease in width comes at the expense of an increase in size, and any such narrow refutations must have exponential length.
Název v anglickém jazyce
A trade-off between length and width in resolution
Popis výsledku anglicky
We describe a family of CNF formulas in n variables, with small initial width, which have polynomial length resolution refutations. By a result of Ben-Sasson and Wigderson it follows that they must also have narrow resolution refutations, of width ... We show that, for our formulas, this decrease in width comes at the expense of an increase in size, and any such narrow refutations must have exponential length.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2016
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Theory of Computing
ISSN
1557-2862
e-ISSN
—
Svazek periodika
12
Číslo periodika v rámci svazku
5
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
14
Strana od-do
1-14
Kód UT WoS článku
000433610000004
EID výsledku v databázi Scopus
2-s2.0-85020472303