A tradeoff between length and width in resolution

Number of the records: 1

1.

SYSNO ASEP	0462811
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	A tradeoff between length and width in resolution
Author(s)	Thapen, Neil (MU-W)_{RID, SAI}
Source Title	Theory of Computing. - : University of Chicago - ISSN 1557-2862 Roč. 12, č. 5 (2016), s. 1-14
Number of pages	14 s.
Language	eng - English
Country	US - United States
Keywords	proof complexity ; resolution ; trade-off
Subject RIV	BA - General Mathematics
OECD category	Pure mathematics
R&D Projects	GBP202/12/G061 GA ČR - Czech Science Foundation (CSF)
Institutional support	MU-W - RVO:67985840
UT WOS	000433610000004
EID SCOPUS	85020472303
DOI	10.4086/toc.2016.v012a005
Annotation	We describe a family of CNF formulas in n variables, with small initial width, which have polynomial length resolution refutations. By a result of Ben-Sasson and Wigderson it follows that they must also have narrow resolution refutations, of width ... We show that, for our formulas, this decrease in width comes at the expense of an increase in size, and any such narrow refutations must have exponential length.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2017

Number of the records: 1