1 results
DICHOTOMY RESULT FOR INDEPENDENCE-FRIENDLY PREFIXES OF GENERALIZED QUANTIFIERS
-
- Journal:
- The Journal of Symbolic Logic / Volume 79 / Issue 4 / December 2014
- Published online by Cambridge University Press:
- 12 December 2014, pp. 1224-1246
- Print publication:
- December 2014
-
- Article
- Export citation
-
We study the expressive power of independence-friendly quantifier prefixes composed of universal
$\left( {\forall x/X} \right)$, existential 
$\left( {\exists x/X} \right)$, and majority quantifiers 
$\left( {Mx/X} \right)$. We provide four quantifier prefixes that can express NP hard properties and show that all quantifier prefixes capable of expressing NP-hard properties embed at least one of these four quantifier prefixes. As for the quantifier prefixes that do not embed any of these four quantifier prefixes, we show that they are equivalent to a first-order quantifier prefix composed of 
$\forall x$, 
$\exists x$, and Mx. In unison, our results imply a dichotomy result: every independence-friendly quantifier prefix is either decidable in LOGSPACE or NP hard.
