On Existentially First-Order Definable Languages and Their Relation to NP (Q4718893)

The authors consider an extended first-order logic, denoted by FOX, which is first-order logic augmented with the additional functions min, max (both 0-ary) and \(+1\) and \(-1\) (both 1-ary). FOX is strictly more powerful than first-order logic on the level of existential definability. A language \(L\) is existentially definable in FOX if there is an existentially quantified sentence of FOX in prenex normal form defining \(L\). The main result of the paper is Theorem 3.4.: Let \(L\) be a regular language. Assuming that \(\text{PH}\) (the polynomial hierarchy) does not collapse, the following holds: (1) \(L-\text{P}=\text{P}\) iff \(L\) is quantifier-free definable in FOX but not trivial; (2) \(L-\text{P}=\text{NP}\) iff \(L\) is existentially but not quantifier-free definable in FOX; (3) \(L-\text{P}=\text{co-NP}\) iff \(L\) is universally but not quantifier-free definable in FOX. The proof of these sentences uses the characterization of the automata of the existentially first-order definable languages. In the final part of the paper some open problems are presented.