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
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references