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.

Under the assumption that the Polynomial-TimeHierarchy does not collapsewe show for a regular language L:the unbalanced polynomial-time leaf language class determined by L equals  iff L is existentially but notquantifierfree definable in FO[<, min, max, +1, −1].Furthermore, no suchclass lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weilcharacterizing the automata of existentially first-order definable languages.