Nondeterminism fairness and a fundamental analogy.
Edith Spaan, Leen Torenvliet, Peter van Emde Boas · 1989
In this note we propose a model for unbounded nondeterministic computation which provides a very natural basis for the structural analogy between recursive function theory and computational complexity theory: P : NP ¸ = REC : RE At the same time this model presents an alternative version of the halting problem which has been known for a decade to be highly intractable. 1 Introduction Structural complexity theory is often presented as the theory in which the results obtained for classes of languages recognized by Turing machines are transferred to a resource bounded setting. Notions like reduction, simplicity, immunity, the arithmetical hierarchy, relativizations etc. were all first defined in recursive function theory and later (relativizations of) these notions were introduced in complexity theory. All of this work was inspired by the frustration originating from the difficulty of the fundamental problem in computational complexity theory which has become known as the P ? = NP pr...