{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:22:43Z","timestamp":1776316963846,"version":"3.50.1"},"reference-count":10,"publisher":"Duke University Press","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[1996,10,1]]},"DOI":"10.1305\/ndjfl\/1040046141","type":"journal-article","created":{"date-parts":[[2003,2,25]],"date-time":"2003-02-25T21:13:08Z","timestamp":1046207588000},"source":"Crossref","is-referenced-by-count":5,"title":["Infinite Versions of Some Problems from Finite Complexity Theory"],"prefix":"10.1215","volume":"37","author":[{"given":"Jeffry L.","family":"Hirst","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"Lempp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"73","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"Beigel, R., and W. Gasarch, \u201cOn the complexity of finding the chromatic number of a recursive graph I: The bounded case,\u201d <i>Annals of Pure and Applied Logic<\/i>, vol. 45 (1989), pp. 1\u201338. Zbl 0685.03033 MR 91b:03076","DOI":"10.1016\/0168-0072(89)90029-8"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Cook, S., \u201cThe complexity of theorem-proving procedures,\u201d pp. 151\u2013158 in <i>Proceedings of the Third Annual ACM Symposium on Theory of Computing<\/i>, ACM, New York, 1971. Zbl 0253.68020","DOI":"10.1145\/800157.805047"},{"key":"3","doi-asserted-by":"crossref","unstructured":"Friedman, H., S. Simpson, and R. Smith, \u201cCountable algebra and set existence axioms,\u201d <i>Annals of Pure and Applied Logic<\/i>, vol. 25 (1983), pp. 141\u2013181. Zbl 0575.03038 MR 85i:03157","DOI":"10.1016\/0168-0072(83)90012-X"},{"key":"4","doi-asserted-by":"crossref","unstructured":"Harel, D., \u201cHamiltonian paths in infinite graphs,\u201d <i>Israel Journal of Mathematics<\/i>, vol. 76 (1991), pp. 317\u2013336. Zbl 0756.05073 MR 93d:68023","DOI":"10.1007\/BF02773868"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Hirst, Tirza, and D. Harel, \u201cTaking it to the limit: On infinite variants of NP-complete problems,\u201d <i>Journal of Computer and System Sciences<\/i>, forthcoming. Zbl 0859.68016 MR 97k:68060","DOI":"10.1006\/jcss.1996.0060"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Karp, R., \u201cReducibility among combinatorial problems,\u201d pp. 85\u2013103 in <i>Complexity of Computer Computations<\/i>, edited by R. Miller and J. Thatcher, Plenum Press, New York, 1972. Zbl 0366.68041 MR 51:14644","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"7","unstructured":"Kaufmann, A., <i>Graphs, Dynamic Programming and Finite Games<\/i>, Academic Press, New York, 1967. Zbl 0161.39201"},{"key":"8","doi-asserted-by":"crossref","unstructured":"Simpson, S., \u201cWhich set existence axioms are needed to prove the Cauchy\/Peano theorem for ordinary differential equations?,\u201d <i>The Journal of Symbolic Logic<\/i>, vol. 49 (1984), pp. 783\u2013802. Zbl 0584.03039 MR 86a:03066","DOI":"10.2307\/2274131"},{"key":"9","unstructured":"Simpson, S., \u201cSubsystems of $Z_2$,\u201d pp. 434\u2013448 in <i>Proof Theory<\/i>, by G. Takeuti, North-Holland, Amsterdam, 1986."},{"key":"10","doi-asserted-by":"crossref","unstructured":"Soare, R., <i>Recursively Enumerable Sets and Degrees<\/i>, Springer-Verlag, Berlin, 1987. Zbl 0667.03030 MR 88m:03003","DOI":"10.1007\/978-3-662-02460-7"}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1040046141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T21:12:54Z","timestamp":1706649174000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-37\/issue-4\/Infinite-Versions-of-Some-Problems-from-Finite-Complexity-Theory\/10.1305\/ndjfl\/1040046141.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10,1]]},"references-count":10,"journal-issue":{"issue":"4","published-online":{"date-parts":[[1996,10,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1040046141","relation":{},"ISSN":["0029-4527"],"issn-type":[{"value":"0029-4527","type":"print"}],"subject":[],"published":{"date-parts":[[1996,10,1]]}}}