Počet záznamů: 1
The space complexity of cutting planes refutations
- 1.0448832 - MÚ 2016 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
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]
Grant CEP: GA ČR GBP202/12/G061
GRANT EU: European Commission(XE) 339691 - FEALORA
Program: FP7
Institucionální podpora: RVO:67985840
Klíčová slova: proof complexity * space * cutting planes
Kód oboru RIV: BA - Obecná matematika
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.
Trvalý link: http://hdl.handle.net/11104/0250451
Název souboru Staženo Velikost Komentář Verze Přístup Pudlak1.pdf 3 476.6 KB Vydavatelský postprint vyžádat
Počet záznamů: 1