On existentially first-order definable languages and their relation to NP
On Existentially First-Order Definable Languages and Their Relation to NP
Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language : the unbalanced polynomial-time leaf language class determined by equals iff 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.
Page 1