{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:11:57Z","timestamp":1782263517545,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_106","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:45:56Z","timestamp":1330195556000},"page":"291-310","source":"Crossref","is-referenced-by-count":1,"title":["The topology of provability in complexity theory"],"prefix":"10.1007","author":[{"given":"Kenneth W.","family":"Regan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. Sublattices of the polynomial-time degrees. STACS '84, Paris, France, April 1984. \/ Inform. and Control 65, April 1985, pp 63\u201384.","DOI":"10.1016\/S0019-9958(85)80020-6"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. Three theorems on polynomial degrees of NP sets. Proc. 26th FOCS, 1985, pp 51\u201355.","DOI":"10.1109\/SFCS.1985.61"},{"issue":"4","key":"22_CR3","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, and R. Solovay. Relativisations of the P=NP? question. SIAM J. Comput. 4, No. 4, 1975, pp 431\u2013442.","journal-title":"SIAM J. Comput."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar and U. Sch\u00f6ning. Bi-immune sets for complexity classes. Math. Syst. Theory 18, 1985.","DOI":"10.1007\/BF01699457"},{"issue":"2","key":"22_CR5","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM J. Comput. 6, No. 2, June 1977, pp 305\u2013321.","journal-title":"SIAM J. Comput."},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0022-0000(78)90034-X","volume":"17","author":"S. Breidtbart","year":"1987","unstructured":"S. Breidtbart. On splitting recursive sets. J. Comp. Sys. Sci. 17, 1987, pp 56\u201364.","journal-title":"J. Comp. Sys. Sci."},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0022-0000(81)90021-0","volume":"22","author":"P. Chew","year":"1981","unstructured":"P. Chew and M. Machtey. A note on structure and looking-back... J. Comp. Sys. Sci. 22, 1981, pp 53\u201359.","journal-title":"J. Comp. Sys. Sci."},{"key":"22_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139171496","volume-title":"Computability","author":"N. Cutland","year":"1980","unstructured":"N. Cutland. Computability. (Cambridge, UK: Camb. University Press, 1980.)"},{"key":"22_CR9","volume-title":"Topology","author":"J. Dugundy","year":"1966","unstructured":"J. Dugundy. Topology. (Boston: Allyn and Bacon, 1966.)"},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0304-3975(79)90046-X","volume":"8","author":"P. Hajek","year":"1979","unstructured":"P. Hajek, Arithmetical hierarchy and complexity of Computation. Theor. Comp. Sci. 8, 1979, pp 227\u2013237.","journal-title":"Theor. Comp. Sci."},{"key":"22_CR11","unstructured":"J. Hartmanis. Feasible computations and provable complexity properties. Monograph, Society for Industrial and Applied Mathematics, 1978."},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"J. Hartmanis. Independence results about context-free languages and lower bounds. Draft, Cornell University, 1984\/Info. Proc. Lett., to appear.","DOI":"10.1016\/0020-0190(85)90026-2"},{"key":"22_CR13","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. (Reading, Mass.: Addison-Wesley, 1979)."},{"key":"22_CR14","first-page":"364","volume":"201","author":"W. Kowalczyk","year":"1984","unstructured":"W. Kowalczyk. Some connections between presentability of complexity classes and the power of formal systems of reasoning. Proc. MFCS '84, Prague, Czechoslovakia, Aug. 1984. Springer LNCS 201, 1984, pp 364\u2013368.","journal-title":"Proc. MFCS '84, Prague, Czechoslovakia, Aug. 1984"},{"key":"22_CR15","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(80)90017-1","volume":"11","author":"D. Kozen","year":"1980","unstructured":"D. Kozen. Indexings of subrecursive classes. Theor. Comp. Sci. 11, 1980, pp 277\u2013301.","journal-title":"Theor. Comp. Sci."},{"issue":"1","key":"22_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. Ladner","year":"1975","unstructured":"R. Ladner. On the structure of polynomial-time reducibility. J.ACM 22, No. 1, 1975, pp 155\u2013171.","journal-title":"J.ACM"},{"key":"22_CR17","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1002\/malq.19750210143","volume":"21","author":"J. Lake","year":"1975","unstructured":"J. Lake. Characterizating the largest countable partial ordering. Zeitschr. f. Math. Logik und Grund-lagen d. Math. 21, 1975, pp 353\u2013354.","journal-title":"Zeitschr. f. Math. Logik und Grund-lagen d. Math."},{"key":"22_CR18","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0304-3975(82)90068-8","volume":"18","author":"D. Leivant","year":"1982","unstructured":"D. Leivant. Unprovability of theorems of complexity theory in weak number theories. Theor. Comp. Sci. 18, 1982, pp 259\u2013268.","journal-title":"Theor. Comp. Sci."},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"S. Mahaney. On the number of isomorphism classes of NP-complete sets. Proc. 22nd FOCS, 1984, pp 271\u2013278.","DOI":"10.1109\/SFCS.1981.30"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"S. Mahaney and P. Young. Orderings of polynomial isomorphism types. Draft, 1983. \/ Theor. Comp. Sci. 39, No. 2, August 1985, pp 207\u2013224.","DOI":"10.1016\/0304-3975(85)90139-2"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"K. Melhorn. Polynomial and abstract subrecursive classes. Proc. 14th FOCS, 1976, pp 96\u2013109.","DOI":"10.1016\/S0022-0000(76)80035-9"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"K. Regan. On diagonalization methods and the structure of language classes. Proc. FCT '83, Borgholm, Sweden. Springer LNCS 158, pp 368\u2013380.","DOI":"10.1007\/3-540-12689-9_119"},{"key":"22_CR23","first-page":"118","volume":"171","author":"K. Regan","year":"1984","unstructured":"K. Regan. Arithmetical degrees of index sets for complexity classes. Proc. Logic & Machines '83, Muenster, W. Germany, May 1983. Springer LNCS 171, 1984, pp 118\u2013130.","journal-title":"Proc. Logic & Machines '83, Muenster, W. Germany, May 1983. Springer LNCS"},{"key":"22_CR24","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers","year":"1967","unstructured":"H. Rogers. Theory of Recursive Functions and Effective Computability. (New York: McGraw-Hill, 1967)."},{"key":"22_CR25","first-page":"77","volume":"171","author":"D. Schmidt","year":"1984","unstructured":"D. Schmidt. On the complement of one complexity class in another. Proc. Logic and Machines '83, ibid. Borgholm, Sweden. Springer LNCS 171, 1984, pp 77\u201387.","journal-title":"Proc. Logic and Machines '83, ibid. Borgholm, Sweden. Springer LNCS"},{"issue":"2\u20133","key":"22_CR26","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0304-3975(85)90217-8","volume":"38","author":"D. Schmidt","year":"1985","unstructured":"D. Schmidt. The recursion-theoretic structure of complexity classes. Theor. Comp. Sci. 38, Nos. 2\u20133, 1985, pp 143\u2013156.","journal-title":"Theor. Comp. Sci."},{"key":"22_CR27","unstructured":"U. Sch\u00f6ning. Untersuchungen zur Struktur von NP... Ph.D. dissertation, University of Stuttgart, 1981."},{"key":"22_CR28","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(82)90114-1","volume":"18","author":"U. Sch\u00f6ning","year":"1982","unstructured":"U. Sch\u00f6ning. A uniform approach to obtain diagonal sets in complexity classes. Theor. Comp. Sci. 18, 1982, pp 95\u2013103.","journal-title":"Theor. Comp. Sci."},{"key":"22_CR29","volume-title":"To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus, and Formalism","author":"A. Visser","year":"1980","unstructured":"A. Visser. Numerations, \u03bb-calculus, and arithmetic. In: To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus, and Formalism. (London\/New York: Academic Press, 1980.)"},{"key":"22_CR30","doi-asserted-by":"crossref","unstructured":"P. Young. Some structural properties of polynomial reducibilities and sets in NP. Proc. 15th STOC, 1983, pp 392\u2013401.","DOI":"10.1145\/800061.808770"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_106.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:27:49Z","timestamp":1742588869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_106","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}