zbMATH — the first resource for mathematics

Infinite versions of some problems from finite complexity theory. (English) Zbl 0882.03041
Summary: Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways.

03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI arXiv
[1] Beigel, R., and W. Gasarch, “On the complexity of finding the chromatic number of a recursive graph I: The bounded case,” Annals of Pure and Applied Logic , vol. 45 (1989), pp. 1–38. · Zbl 0685.03033
[2] Cook, S., “The complexity of theorem-proving procedures,” pp. 151–158 in Proceedings of the Third Annual ACM Symposium on Theory of Computing , ACM, New York, 1971. · Zbl 0253.68020
[3] Friedman, H., S. Simpson, and R. Smith, “Countable algebra and set existence axioms,” Annals of Pure and Applied Logic , vol. 25 (1983), pp. 141–181. · Zbl 0575.03038
[4] Harel, D., “Hamiltonian paths in infinite graphs,” Israel Journal of Mathematics , vol. 76 (1991), pp. 317–336. · Zbl 0756.05073
[5] Hirst, Tirza, and D. Harel, “Taking it to the limit: On infinite variants of NP-complete problems,” Journal of Computer and System Sciences , forthcoming. · Zbl 0859.68016
[6] Karp, R., “Reducibility among combinatorial problems,” pp. 85–103 in Complexity of Computer Computations , edited by R. Miller and J. Thatcher, Plenum Press, New York, 1972. · Zbl 0366.68041
[7] Kaufmann, A., Graphs, Dynamic Programming and Finite Games , Academic Press, New York, 1967. · Zbl 0161.39201
[8] Simpson, S., “Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?,” The Journal of Symbolic Logic , vol. 49 (1984), pp. 783–802. JSTOR: · Zbl 0584.03039
[9] Simpson, S., “Subsystems of \(Z_2\),” pp. 434–448 in Proof Theory , by G. Takeuti, North-Holland, Amsterdam, 1986. · Zbl 0609.03019
[10] Soare, R., Recursively Enumerable Sets and Degrees , Springer-Verlag, Berlin, 1987. · Zbl 0667.03030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.