Characterization of realizable space complexities
type: Item
instance of: scholarly article
title: Characterization of realizable space complexities
zbMATH Open document ID: 0826.03019
DOI: 10.1016/0168-0072(94)00026-Y
author: Albert R. Meyer
author: Joel I. Seiferas
published in: Annals of Pure and Applied Logic
publication date: 1995-07-03T00:00:00Z
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 768741
zbMATH Keywords: inherent space complexity
zbMATH Keywords: partial function
zbMATH Keywords: specification
MaRDI profile type: Publication
cites work: A Machine-Independent Theory of the Complexity of Recursive Functions
cites work: On Effective Procedures for Speeding Up Algorithms
cites work: Computational Complexity and the Existence of Complexity Gaps
cites work: The Operator Gap
cites work: Q5592246
cites work: Q4060387
cites work: Computational complexity of functions
cites work: “Helping”: several formalizations
cites work: Q4153600
cites work: Computational speed-up by effective operators
cites work: Q4197342
cites work: Gödel numberings of partial recursive functions
cites work: Q5573961
cites work: A characterization of complexity sequences
cites work: Relating refined space complexity classes
cites work: Halting space-bounded computations
cites work: Q5636862
cites work: Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
full work available at URL: 0168-0072(94)00026-y
OpenAlex ID: W2091585331
Recommended article: Q4229136
Recommended article: Extension complexity and realization spaces of hypersimplices
Recommended article: The Complexity of Metric Realization
Recommended article: THE A-COMPLEXITY OF A SPACE
Recommended article: Dimension characterizations of complexity classes
Recommended article: Dimension Characterizations of Complexity Classes
Recommended article: Complexity analysis via approach spaces
Recommended article: Complexity spaces as quantitative domains of computation
Recommended article: An infinitesimal characterization of the complexity of homogeneous spaces
Recommended article: A survey on real structural complexity theory
description: scientific article; zbMATH DE number 768741