Henkin Quantifiers and Complete Problems

  • Andreas Blass ,
  • Yuri Gurevich

Annals of Pure and Applied Logic 32 (1986), 1-16 | , Vol 32

Download BibTex

We show that almost any non-linear quantifier, applied to quantifier-free first-order formulas, suffices to express an NP- complete predicate; the remaining non-linear quantifiers express exactly co-NL predicates (NL is Nondeterministic Log-space).