From determinism, non-determinism and alternation to recursion schemes for P, NP and Pspace

摘要

Our goal is to approach the classes of computational complexity P, NP, and Pspace in a recursion-theoretic manner. Here we emphasize the connection between the structure of the recursion schemes and the underlying models of computation.