A tradeoff between length and width in resolution (Q2816413)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: scientific article |
scientific article; zbMATH DE number 6618610
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A tradeoff between length and width in resolution |
scientific article; zbMATH DE number 6618610 |
Statements
22 August 2016
0 references
proof complexity
0 references
resolution
0 references
width
0 references
trade-off
0 references
reflection
0 references
lower bound
0 references
tradeoff between length and width
0 references
A tradeoff between length and width in resolution (English)
0 references
In this paper, the author investigates the connection between the length of the resolution refutation and its width. Since any short refutation can be transformed into a ``narrow'' one, the author shows that the ``narrow'' refutation must be essential longer than the initial short refutation.NEWLINENEWLINE The author describes a family of CNF-formulas with small width which have a refutation of polynomial length and shows that the corresponding ``narrow'' refutation must be of an exponential length. The CNF-formulas described in the paper are a propositional version of the colored polynomial local search principle.
0 references
