A Combinatorial Approach to Complexity Theory via Ordinal Hierarchies

DOI10.1017/S0963548300001103zbMath0814.03032MaRDI QIDQ4305315

W. Thumser, Walter A. Deuber

Publication date: 13 June 1995

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

well-quasi-orderingGrzegorczyk-Wainer hierarchyregressive sequence

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Cites Work

• On Gödel incompleteness and finite combinatorics
• Some bounds for the Ramsey-Paris-Harrington numbers
• Combinatorial theorems on contractive mappings in power sets
• Fast growing functions based on Ramsey theorems
• The theory of well-quasi-ordering: a frequently discovered concept
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
• A Combinatorial Theorem
• On the interpretation of non-finitist proofs–Part II
• Ordering by Divisibility in Abstract Algebras
• The consistency of arithmetics

This page was built for publication: A Combinatorial Approach to Complexity Theory via Ordinal Hierarchies