ON NONDETERMINISM IN MACHINES AND LANGUAGES

Non-deterministic computation is not really computation, but the diffe rence with real computation is blurred. We study in detail various lev els of non-determinism in computations on non-deterministic Turing mac hines with polynomial bounds on the resources. Meanwhile, we consider numerous query languages, implicit logic, choice logic, order invarian t logic, and restrictions of second-order logic, and establish corresp ondences between all these formalisms for both deterministic and non-d eterministic queries. To the degrees of non-determinism in the computa tions, correspond levels of non-determinism in the logical definitions . Our main contribution is to characterize various complexity classes between PTIME and PSPACE, by several logical means, thus translating o pen questions in complexity theory to open questions in logic related to the use of the nondeterminism.