Classifying the phase transition threshold for Ackermannian functions

DOI10.1016/j.apal.2007.02.004zbMath1160.03021MaRDI 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 transition; threshold; Ackermann function; fast growing hierarchy

Mathematics Subject Classification ID

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

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D20: Recursive functions and relations, subrecursive hierarchies

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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