Classifying the phase transition threshold for Ackermannian functions

DOI10.1016/j.apal.2007.02.004zbMath1160.03021OpenAlexW2082669687MaRDI QIDQ1012327

Eran Omri, Andreas Weiermann

Publication date: 16 April 2009

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://biblio.ugent.be/publication/547642

zbMATH Keywords

phase transitionthresholdAckermann functionfast growing hierarchy

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (3)

Phase Transitions for Weakly Increasing Sequences ⋮ Phase transitions for Gödel incompleteness ⋮ Partitioning 𝛼–large sets: Some lower bounds

Cites Work

• Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers
• Theories of computational complexity
• Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results
• An extremely sharp phase transition threshold for the slow growing hierarchy
• Phase transition thresholds for some Friedman-style independence results
• A Uniform Approach to Fundamental Sequences and Hierarchies
• A classification of rapidly growing Ramsey functions
• An application of graphical enumeration to PA *
• A classification of the ordinal recursive functions
• Eine Klassifikation der ε₀‐Rekursiven Funktionen
• Logical Approaches to Computational Barriers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Classifying the phase transition threshold for Ackermannian functions