A recursion-theoretic approach to NP

Annals of Pure and Applied Logic 162 (8):661-666 (2011)
  Copy   BIBTEX

Abstract

An implicit characterization of the class NP is given, without using any minimization scheme. This is the first purely recursion-theoretic formulation of NP

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2011.01.010

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,907

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Quantum hypercomputation—hype or computation?Amit Hagar & Alex Korolev - 2007 - Philosophy of Science 74 (3):347-363.
Recursion-theoretic hierarchies.Peter G. Hinman - 1978 - New York: Springer Verlag.
Degrees of Relative Provability.Mingzhong Cai - 2012 - Notre Dame Journal of Formal Logic 53 (4):479-489.
Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.
Recursion theory and the lambda-calculus.Robert E. Byerly - 1982 - Journal of Symbolic Logic 47 (1):67-83.
General recursion theory: an axiomatic approach.Jens Erik Fenstad - 1980 - New York: Springer Verlag.
Recursive constructions in topological spaces.Iraj Kalantari & Allen Retzlaff - 1979 - Journal of Symbolic Logic 44 (4):609-625.
Minimal α-recursion theoretic degrees.John M. MacIntyre - 1973 - Journal of Symbolic Logic 38 (1):18-28.
Two recursion theoretic characterizations of proof speed-ups.James S. Royer - 1989 - Journal of Symbolic Logic 54 (2):522-526.
Definability of R. E. sets in a class of recursion theoretic structures.Robert E. Byerly - 1983 - Journal of Symbolic Logic 48 (3):662-669.
Recursion theory on orderings. I. a model theoretic setting.G. Metakides & J. B. Remmel - 1979 - Journal of Symbolic Logic 44 (3):383-402.
Universal recursion theoretic properties of R.e. Preordered structures.Franco Montagna & Andrea Sorbi - 1985 - Journal of Symbolic Logic 50 (2):397-406.
Gunk, Topology and Measure.Frank Arntzenius - 2004 - In Dean Zimmerman (ed.), Oxford Studies in Metaphysics: Volume 4. Oxford University Press.
What is Radical Recursion?Steven M. Rosen - 2004 - SEED Journal 4 (1):38-57.

Analytics

Added to PP
2013-10-27

Downloads
13 (#1,061,253)

6 months
1 (#1,508,411)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Characterizing PSPACE with pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Characterizing NC with tier 0 pointers.Isabel Oitavem - 2004 - Mathematical Logic Quarterly 50 (1):9.
Characterizing PSPACE with pointers.Isabel Oitavern - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Characterizing NC with tier 0 pointers.Isabel Oitavern - 2004 - Mathematical Logic Quarterly 50 (1):9-17.

Add more references