Theories of computational complexity

zbMath0633.03034MaRDI QIDQ1210716

Cristian S. Calude

Publication date: 5 June 1993

Published in: Annals of Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

recursive functionsGödel numberingsAckermann's functionabstract complexity theoryBlum's complexity theoryKolmogorov's complexity theoryLOOP-hierarchyLOOP-languageMartin-Löf's complexity theorySubrecursive hierarchiesSudan's function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Recursive functions and relations, subrecursive hierarchies (03D20) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

On recursive bounds for the exceptional values in speed-up, A Note on Blum Static Complexity Measures, Invariance and Universality of Complexity, Is complexity a source of incompleteness?, Turing completeness of water computing, Constructive mathematics and unbounded operators -- a reply to Hellman, The intrinsic difficulty of recursive functions, Language-theoretic complexity of disjunctive sequences, Randomness as an invariant for number representations, Some Hierarchies of Primitive Recursive Functions on Term Algebras, SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS, A parametric worst-case approach to fairness in cooperative games with transferable utility, COMPLEXITY, INFORMATION, ENERGY, Relativized topological size of sets of partial recursive functions, Unnamed Item, Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers, Effective category and measure in abstract complexity theory, On the power of several queues, If not empty, NP-P is topologically large, Note on the topological structure of random strings, Effective category and measure in abstract complexity theory, Unnamed Item, Unnamed Item, Speed-up theorems in type-2 computations using oracle Turing machines, Is independence an exception?, Classifying the phase transition threshold for Ackermannian functions, Constructive chaos by cellular automata and possible sources of an arrow of time, Determining and stationary sets for some classes of partial recursive functions, Kolmogorov-Complexity Based on Infinite Computations, Incompleteness, Undecidability and Automated Proofs, Regressive Ramsey numbers are Ackermannian