Isabel Oitavem (FCT-UNL and CMAF-UL), NP with tier 0 pointers.
Schedule
- Jan. 30, 2012, 16:00 - 16:30
Abstract
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.
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.