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 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.
On extremum-searching approximate probabilistic algorithms
On pseudo-random sequences and their relation to a class of stochastical laws
On the complexity of computable real sequences
On the complexity of the word problem for finitely presented commutative semigroups.
On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra.
On the restricted equivalence for subclasses of propositional logic