The space complexity of cutting planes refutations
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00448832" target="_blank" >RIV/67985840:_____/15:00448832 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.CCC.2015.433" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.CCC.2015.433</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CCC.2015.433" target="_blank" >10.4230/LIPIcs.CCC.2015.433</a>
Alternative languages
Result language
angličtina
Original language name
The space complexity of cutting planes refutations
Original language description
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 verifyingit. Our main result is that any unsatisfable set of inequalities has a cutting planes refutation in space five.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
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
30th Conference on Computational Complexity (CCC 2015)
ISBN
978-3-939897-81-1
ISSN
1868-8969
e-ISSN
—
Number of pages
15
Pages from-to
433-447
Publisher name
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl
Event location
Portland
Event date
Jun 17, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—