Infinite versions of some problems from finite complexity theory

DOI10.1305/NDJFL/1040046141MaRDI QIDQ1374209zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: Recently, connections have been explored between the complexity of finite problems in graph theory and the complexity of their infinite counterparts. As is shown in our paper (and in independent work of Tirza Hirst and D. Harel from a different angle) there is no firm connection between these complexities, namely finite problems of equal complexity can have radically different complexity for the infinite versions and vice versa. Furthermore, the complexity of an infinite counterpart can depend heavily on precisely how the finite problem is rephrased in the infinite case. The finite problems we address include colorability of graphs and existence of subgraph isomorphisms. In particular, we give three infinite versions of the 3-colorability problem that vary considerably in their recursion theoretic and proof theoretic complexity. Additionally, we show that three subgraph isomorphism problems of varying finite complexity have infinite versions with identical recursion theoretic and proof theoretic content.

Recommendations

• Taking it to the limit: On infinite variants of NP-complete problems
• Incompleteness in the finite domain
• The exact complexity of the infinite Post Correspondence Problem
• P NP for infinite time Turing machines
• scientific article; zbMATH DE number 1759437

Cites work

• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• Countable algebra and set existence axioms
• Graphs, dynamic programming, and finite games
• Hamiltonian paths in infinite graphs
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• Proof theory. 2nd ed
• Taking it to the limit: On infinite variants of NP-complete problems
• The complexity of theorem-proving procedures
• Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?

Cited in

(14)

• The Complexity of Infinite Computations In Models of Set Theory
• The complexity of finding supergraphs
• Incompleteness in the finite domain
• Reverse mathematics and Weihrauch analysis motivated by finite complexity theory
• Domatic partitions of computable graphs
• Infinite computations and the generic finite
• Finitely repeated search and the diamond paradox
• Undecidability of infinite Post correspondence problem for instances of size 8
• scientific article; zbMATH DE number 4104214 (Why is no real title available?)
• Infinite time extensions of Kleene's \({\mathcal O}\)
• Undecidability of infinite post correspondence problem for instances of Size 9
• The complexity of recursive constraint satisfaction problems
• scientific article; zbMATH DE number 1759437 (Why is no real title available?)
• Definable inapproximability: new challenges for duplicator

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1374209)