A recursion-theoretic approach to NP

Research output: Other contribution


We give a characterization of NP using a recursion scheme with tier 0 pointers. This extends the Bellantoni–Cook characterization of Ptime and, simultaneously, it is a restriction of a recursion-theoretic characterization of Pspace.
Original languageUnknown
Publication statusPublished - 1 Jan 2014

Cite this