Space complexity in polynomial calculus

0385827 - MÚ 2013 RIV US eng C - Conference Paper (international conference)
Filmus, Y. - Lauria, M. - Norström, J. - Thapen, Neil - Ron-Zewi, N.
Space complexity in polynomial calculus.
2012 IEEE 27th Annual Conference on Computational Complexity (CCC). New York: IEEE, 2012, s. 334-344. Annual IEEE Conference on Computational Complexity. ISBN 978-0-7695-4708-4. ISSN 1093-0159.
[27th Annual IEEE Conference on Computational Complexity (CCC). Porto (PT), 26.06.2012-29.06.2012]
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : cutting-plane proofs * lower bounds * hard examples
Subject RIV: BA - General Mathematics
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6243410

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.
Permanent Link: http://hdl.handle.net/11104/0007486