Infinite versions of some problems from finite complexity theory

DOI10.1305/ndjfl/1040046141zbMath0882.03041arXivmath/9503205OpenAlexW2005490762MaRDI QIDQ1374209

Jeffry L. Hirst, Steffen Lempp

Publication date: 12 March 1998

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9503205

zbMATH Keywords

finite objectsinfinite objectsproof theoretic strengthrecursion theoretic complexity

Mathematics Subject Classification ID

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

Related Items (3)

Reverse mathematics and Weihrauch analysis motivated by finite complexity theory ⋮ The complexity of finding supergraphs ⋮ Domatic partitions of computable graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Countable algebra and set existence axioms
• Proof theory. 2nd ed
• Hamiltonian paths in infinite graphs
• Taking it to the limit: On infinite variants of NP-complete problems
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• Graphs, dynamic programming, and finite games
• Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?
• The complexity of theorem-proving procedures

This page was built for publication: Infinite versions of some problems from finite complexity theory