Hard examples for resolution (Q3780485)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4043296
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Hard examples for resolution |
scientific article; zbMATH DE number 4043296 |
Statements
Hard examples for resolution (English)
0 references
1987
0 references
pigeonhole clauses
0 references
mechanical theorem proving
0 references
complexity of proofs
0 references
hard examples
0 references
resolution proofs
0 references
expander graphs
0 references
refutations
0 references
0.8743531
0 references
0.8496065
0 references
0 references
0 references
0.8018288
0 references
0.8004902
0 references
0.79205096
0 references
0 references
0.78191435
0 references
0 references
The paper proves that there is an infinite sequence of graph-based sets of clauses of length O(n), that require resolution refutations of length at least c n, for a fixed \(c>1.\) The author considers a sequence of graphs, obtained from the expander graphs originally defined by \textit{G. A. Margulis} [Probl. Inf. Transm. 9, 325-332 (1973); translated from Probl. Peredachi Inf. 9, No.4, 71-80 (1973; Zbl 0312.22011)]. Then he defines the set of clauses by the use of these graphs. The lower bound is proved by the technique first used by \textit{A. Haken} [Theor. Comput. Sci. 39, 297-308 (1985; Zbl 0586.03010)], who studied the ``pigeonhole'' clauses. The study of graph-based clauses by the use of Haken's method, enables the author to improve on the results concerning the length of minimal refutations of contradictory sets of clauses, in several respects. So, the lower bound is the best possible, except for the choice of the constant c. Then the author proves that his set of clauses has a refutation of length O(n 4) in Kleene's axiomatic system for propositional calculus. The ``pigeonhole'' clauses are not known to have short (polynomial-length) proofs in a standard axiomatic system for the propositional calculus. And last, the author observes how the proof can be modified, to show an exponential lower bound for resolution refutations for sets of clauses in which each clause contains three literals (the ``pigeonhole'' clauses contain clauses of length n).
0 references