The space complexity of cutting planes refutations

Number of the records: 1

1.

SYSNO ASEP	0448832
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	The space complexity of cutting planes refutations
Author(s)	Galesi, N. (IT) Pudlák, Pavel (MU-W)_{RID, SAI} Thapen, Neil (MU-W)_{RID, SAI}
Source Title	30th Conference on Computational Complexity (CCC 2015). - Dagstuhl : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2015 / Zuckerman D. - ISSN 1868-8969 - ISBN 978-3-939897-81-1
Pages	s. 433-447
Number of pages	15 s.
Publication form	Print - P
Action	Conference on Computational Complexity (CCC) /30./
Event date	17.06.2015-19.06.2015
VEvent location	Portland
Country	US - United States
Event type	WRD
Language	eng - English
Country	DE - Germany
Keywords	proof complexity ; space ; cutting planes
Subject RIV	BA - General Mathematics
R&D Projects	GBP202/12/G061 GA ČR - Czech Science Foundation (CSF)
Institutional support	MU-W - RVO:67985840
EID SCOPUS	84958236932
DOI	10.4230/LIPIcs.CCC.2015.433
Annotation	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.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2016

Number of the records: 1