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 (31)

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

This page was built for publication: Theories of computational complexity