A Feasibly Constructive Lower Bound for Resolution Proofs

Stephen A. Cook, Toniann PitassiInf. Process. Lett 1990 · OpenReview

Abstract

Motivated by improved SAT algorithms ((O. Kullmann, DIMACS Series, vol. 35, Amer. Math. Soc., Providence, RI, 1997; O. Kullmann, Theoret. Comput. Sci. (1999); O. Kullmann, Inform. Comput., submitted); yielding new worst-case upper bounds) a natural parameterized generalization GER of Extended Resolution (ER) is introduced. ER can simulate polynomially GER, but GER allows special cases for which exponential lower bounds can be proven.
BibTeX
@inproceedings{cook1990feasibly,
  author = {Stephen A. Cook and Toniann Pitassi},
  title = {{A Feasibly Constructive Lower Bound for Resolution Proofs}},
  booktitle = {Inf. Process. Lett},
  year = {1990},
  url = {https://openreview.net/forum?id=pEAVLAqBrg},
}

Loading related content...

Figure