On Existentially First-Order Definable Languages and Their Relation to NP
Bernd Borchert, Dietrich Kuske, Frank Stephan · Lecture notes in computer science · 1998
Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals iff L is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.