Infinite versions of some problems from finite complexity theory

DOI10.1305/NDJFL/1040046141zbMATH Open0882.03041arXivmath/9503205OpenAlexW2005490762MaRDI QIDQ1374209FDOQ1374209

Jeffry L. Hirst, Steffen Lempp

Publication date: 12 March 1998

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

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.

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

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\neq NP\) for infinite time Turing machines
• scientific article; zbMATH DE number 1759437

zbMATH Keywords

finite objectsinfinite objectsproof theoretic strengthrecursion theoretic complexity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• The complexity of finding supergraphs
• 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
• Title not available (Why is that?)
• Infinite time extensions of Kleene's \({\mathcal O}\)
• Undecidability of infinite post correspondence problem for instances of Size 9
• Title not available (Why is that?)
• Definable inapproximability: new challenges for duplicator
• The Complexity of Infinite Computations In Models of Set Theory

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)