The space complexity of cutting planes refutations

0448832 - MÚ 2016 RIV DE eng C - Conference Paper (international conference)
Galesi, N. - Pudlák, Pavel - Thapen, Neil
The space complexity of cutting planes refutations.
30th Conference on Computational Complexity (CCC 2015). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2015 - (Zuckerman, D.), s. 433-447. Leibniz International Proceedings in Informatics, 33. ISBN 978-3-939897-81-1. ISSN 1868-8969.
[Conference on Computational Complexity (CCC) /30./. Portland (US), 17.06.2015-19.06.2015]
R&D Projects: GA ČR GBP202/12/G061
EU Projects: European Commission(XE) 339691 - FEALORA
Program: FP7
Institutional support: RVO:67985840
Keywords : proof complexity * space * cutting planes
Subject RIV: BA - General Mathematics
http://drops.dagstuhl.de/opus/volltexte/2015/5055/

We study the space complexity of the cutting planes proof system, in which the lines in a proof are integral linear inequalities. We measure the space used by a refutation as the number of inequalities that need to be kept on a blackboard while verifying it. Our main result is that any unsatisfable set of inequalities has a cutting planes refutation in space five.
Permanent Link: http://hdl.handle.net/11104/0250451