A recursion-theoretic approach to NP

Isabel Maria Oitavem Fonseca da Rocha Kahle

A recursion-theoretic approach to NP

Isabel Maria Oitavem Fonseca da Rocha Kahle

DM - Departamento de Matemática

Research output: Other contribution

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.

Original language	Unknown
Volume	20
Publication status	Published - 1 Jan 2014

Cite this

@misc{f5b71d2607484fdc99cdb009d2ffaa22,

title = "A recursion-theoretic approach to NP",

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.",

author = "Kahle, {Isabel Maria Oitavem Fonseca da Rocha}",

year = "2014",

month = jan,

day = "1",

language = "Unknown",

volume = "20",

type = "Other",

}

TY - GEN

T1 - A recursion-theoretic approach to NP

AU - Kahle, Isabel Maria Oitavem Fonseca da Rocha

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

M3 - Other contribution

VL - 20

ER -