Space complexity in polynomial calculus
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Space complexity in polynomial calculus
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
2012 IEEE 27th Annual Conference on Computational Complexity (CCC)
ISBN
978-0-7695-4708-4
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
334-344
Publisher name
IEEE
Place of publication
New York
Event location
Porto
Event date
Jun 26, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000308976600035