Space complexity in polynomial calculus

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F12%3A00385827" target="_blank" >RIV/67985840:_____/12:00385827 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1109/CCC.2012.27" target="_blank" >http://dx.doi.org/10.1109/CCC.2012.27</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/CCC.2012.27" target="_blank" >10.1109/CCC.2012.27</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Space complexity in polynomial calculus

Popis výsledku v původním jazyce

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving. For the polynomial calculus proof system, the only previously known space lower bound is for CNF formulas of unbounded width in [Alekhnovich et al. '02], where the lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could refute any k-CNF formula in constant space.

Název v anglickém jazyce

Space complexity in polynomial calculus

Popis výsledku anglicky

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving. For the polynomial calculus proof system, the only previously known space lower bound is for CNF formulas of unbounded width in [Alekhnovich et al. '02], where the lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could refute any k-CNF formula in constant space.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

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ů

Název statě ve sborníku

2012 IEEE 27th Annual Conference on Computational Complexity (CCC)

ISBN

978-0-7695-4708-4

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

334-344

Název nakladatele

IEEE

Místo vydání

New York

Místo konání akce

Porto

Datum konání akce

26. 6. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000308976600035