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 functions; Gödel numberings; Ackermann's function; abstract complexity theory; Blum's complexity theory; Kolmogorov's complexity theory; LOOP-hierarchy; LOOP-language; Martin-Löf's complexity theory; Subrecursive hierarchies; Sudan's function

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations

03D15: Complexity of computation (including implicit computational complexity)

68-02: Research exposition (monographs, survey articles) pertaining to computer science

03D20: Recursive functions and relations, subrecursive hierarchies

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

Related Items

Some Hierarchies of Primitive Recursive Functions on Term Algebras, SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS, Unnamed Item, Effective category and measure in abstract complexity theory, On the power of several queues, If not empty, NP-P is topologically large, Constructive chaos by cellular automata and possible sources of an arrow of time, Determining and stationary sets for some classes of partial recursive functions, Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers, Relativized topological size of sets of partial recursive functions, Note on the topological structure of random strings, Regressive Ramsey numbers are Ackermannian, On recursive bounds for the exceptional values in speed-up, Language-theoretic complexity of disjunctive sequences, Is independence an exception?, Constructive mathematics and unbounded operators -- a reply to Hellman, The intrinsic difficulty of recursive functions, Is complexity a source of incompleteness?, COMPLEXITY, INFORMATION, ENERGY