Characterization of realizable space complexities

&
Annals of Pure and Applied Logic 73 (2):171-190 (1995)
  Copy   BIBTEX

Abstract

This is a complete exposition of a tight version of a fundamental theorem of computational complexity due to Levin: The inherent space complexity of any partial function is very accurately specifiable in a Π1 way, and every such specification that is even Σ2 does characterize the complexity of some partial function, even one that assumes only the values 0 and 1

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(94)00026-y

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,783

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

Retracts of the closure space of filters in the lattice of all subsets.Andrzej W. Jankowski - 1986 - Studia Logica 45 (2):135 - 154.
Priestley duality for some subalgebra lattices.Georges Hansoul - 1996 - Studia Logica 56 (1-2):133 - 149.
Spheres are not multiply realizable.Colin Klein - unknown
A characterization of logical constants is possible.Gila Sher - 2003 - Theoria 18 (2):189-198.
Concepts of space: the history of theories of space in physics.Max Jammer - 1993 - New York: Dover Publications.
A term rewriting characterization of the functions computable in polynomial space.Isabel Oitavem - 2002 - Archive for Mathematical Logic 41 (1):35-47.
Adequate ideas and modest scepticism in Hume's metaphysics of space.Donald C. Ainslie - 2010 - Archiv für Geschichte der Philosophie 92 (1):39-67.
Dynamic topological logic of metric spaces.David Fernández-Duque - 2012 - Journal of Symbolic Logic 77 (1):308-328.
A note on information theoretic characterizations of physical theories.Hans Halvorson - 2003 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 35 (2):277-293.
Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces.Bettina Klaus - 2001 - Theory and Decision 51 (1):13-29.
Where's the Beef? Phenomenal Concepts as Both Demonstrative and Substantial.Robert Schroer - 2010 - Australasian Journal of Philosophy 88 (3):505-522.
Universality of the closure space of filters in the algebra of all subsets.Andrzej W. Jankowski - 1985 - Studia Logica 44 (1):1 - 9.

Analytics

Added to PP
2014-01-16

Downloads
13 (#1,034,116)

6 months
5 (#632,816)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Gödel numberings of partial recursive functions.Hartley Rogers - 1958 - Journal of Symbolic Logic 23 (3):331-341.
A characterization of complexity sequences.C. P. Schnorr & G. Stumpf - 1975 - Mathematical Logic Quarterly 21 (1):47-56.
“Helping”: several formalizations.Nancy Lynch - 1975 - Journal of Symbolic Logic 40 (4):555-566.

View all 6 references / Add more references