{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:49:03Z","timestamp":1725662943125},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540164869"},{"type":"electronic","value":"9783540398257"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_109","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:46:12Z","timestamp":1330195572000},"page":"330-346","source":"Crossref","is-referenced-by-count":6,"title":["Diagonalisation methods in a polynomial setting"],"prefix":"10.1007","author":[{"given":"Leen","family":"Torenvliet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Emde Boas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker T., J. Gill & R. Solovay, Relativisations of the P vs. NP question, SIAM J. Comp. 4 (1975) 431\u2013442","journal-title":"SIAM J. Comp."},{"key":"25_CR2","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(79)90043-4","volume":"8","author":"T. Baker","year":"1979","unstructured":"Baker T. & A. Selman, A second step toward the polynomial hierarchy, Theoretical Computer Science 8 (1979) 177\u2013187.","journal-title":"Theoretical Computer Science"},{"key":"25_CR3","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1137\/0214012","volume":"14","author":"J.L. Balcazar","year":"1985","unstructured":"Balcazar J.L., Simplicity, Relativisations & Nondeterminism, SIAM J. Comp. 14 (1985) 148\u2013157","journal-title":"SIAM J. Comp."},{"key":"25_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BFb0030286","volume":"176","author":"J.L. Balcazar","year":"1984","unstructured":"Balcazar J.L., Separating, Strongly Separating and Collapsing Relativised Complexity Classes, Proc. MFCS(Invited Lecture), Lecture Notes in Computer Science 176 (1984) 1\u201316.","journal-title":"Proc. MFCS(Invited Lecture), Lecture Notes in Computer Science"},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennet","year":"1981","unstructured":"Bennet C. & J. Gill, Relative to a Random Oracle P\u2249NP with probability 1, SIAM J. Comp. 10 (1981) 96\u2013113.","journal-title":"SIAM J. Comp."},{"key":"25_CR6","unstructured":"Book R.V., Separating Relativised Complexity Classes, to appear."},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/3-540-16078-7_86","volume":"210","author":"J. Hartmanis","year":"1986","unstructured":"Hartmanis J. & L. Hemachandra, On Sparse Oracles Separating Feasible Complexity Classes, Proc. 3d annual STACS, Lecture Notes in Computer Science 210 (1986) 321\u2013333.","journal-title":"Proc. 3d annual STACS, Lecture Notes in Computer Science"},{"key":"25_CR8","unstructured":"Heller H., On Relativised Exponential and Probabilistic Complexity Classes, to appear."},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Homer S., On Simple and Creative Sets in NP, manuscript (1985).","DOI":"10.1007\/3-540-17179-7_25"},{"key":"25_CR10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0304-3975(83)90003-8","volume":"24","author":"S. Homer","year":"1983","unstructured":"Homer S. & W. Maass, Oracle Dependent Properties of the Lattice of NP Sets, Theoretical Computer Science 24 (1983) 279\u2013289.","journal-title":"Theoretical Computer Science"},{"key":"25_CR11","first-page":"344","volume":"15","author":"R. Kannan","year":"1983","unstructured":"Kannan R., Alternation and the power of nondeterminism, Proc. ACM SIGACT STOC 15 (1983) 344\u2013346.","journal-title":"Proc. ACM SIGACT STOC"},{"key":"25_CR12","first-page":"235","volume":"22","author":"R. Kannan","year":"1983","unstructured":"Kannan R., Towards separating Nondeterministic Time from Deterministic Time, Proc. IEEE FOCS 22 (1983) 235\u2013243.","journal-title":"Proc. IEEE FOCS"},{"key":"25_CR13","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0209003","volume":"9","author":"C.M.R. Kintala","year":"1980","unstructured":"Kintala C.M.R., and P. Fischer, Refining Nondeterminism in Relativised Polynomial Time Bounded Computations, SIAM J. Comp. 9 (1980) 46\u201353.","journal-title":"SIAM J. Comp."},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1090\/S0002-9947-1943-0007371-8","volume":"53","author":"S.C. Kleene","year":"1943","unstructured":"Kleene S.C., Recursive predicates and quantifiers, Trans. Am. Math. Soc. 53 (1943) 41\u201373.","journal-title":"Trans. Am. Math. Soc."},{"key":"25_CR15","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(80)90017-1","volume":"11","author":"D. Kozen","year":"1980","unstructured":"Kozen D., Indexing of Subrecursive Languages, Theoretical Computer Science 11(1980) 277\u2013301.","journal-title":"Theoretical Computer Science"},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1137\/0214008","volume":"14","author":"S. Kurtz","year":"1985","unstructured":"Kurtz S., Sparse Sets in NP-P: Relativisations, SIAM J. Comp. 14 (1985) 113\u2013119.","journal-title":"SIAM J. Comp."},{"key":"25_CR17","first-page":"429","volume":"24","author":"W. Paul","year":"1983","unstructured":"Paul W., N. Pippenger, E. Szemer\u00e9di & W. Trotter, On determinism versus nondeterminism and related problems, Proc. IEEE FOCS 24 (1983) 429\u2013438.","journal-title":"Proc. IEEE FOCS"},{"key":"25_CR18","first-page":"368","volume":"158","author":"K. Regan","year":"1983","unstructured":"Regan K., On diagonalisation methods and the structure of language classes, Proc. 1983 FCT Conference, Lecture Notes in Computer Science 158 (1983) 368\u2013380.","journal-title":"Proc. 1983 FCT Conference, Lecture Notes in Computer Science"},{"key":"25_CR19","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1137\/0212037","volume":"12","author":"A.L. Selman","year":"1983","unstructured":"Selman A.L., Xu Mei-Rui & R.V. Book, Positive Relativisations of Complexity Classes, SIAM J. Comp. 12 (1983) 565\u2013579.","journal-title":"SIAM J. Comp."},{"key":"25_CR20","unstructured":"Schoening U., Relativisations and infinite subsets of NP sets, Unpublished Manuscript (1982)."},{"key":"25_CR21","unstructured":"Soare R.I., Recursively Enumerable Sets and Degrees: The Study of Computable Functions and Computably Generated Sets, to appear in Springer \u03a9 series."},{"key":"25_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"Stockmeyer L.J., The Polynomial-time Hierarchy, Theoretical Computer Science 3 (1976) 1\u201322.","journal-title":"Theoretical Computer Science"},{"key":"25_CR23","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BFb0024022","volume":"182","author":"L. Torenvliet","year":"1985","unstructured":"Torenvliet L. & P. van Emde Boas, Combined Simplicity and Immunity in Relativised NP, Proc. 2nd annual STACS, Lecture Notes in Computer Science 182 (1985) 339\u2013350.","journal-title":"Proc. 2nd annual STACS, Lecture Notes in Computer Science"},{"key":"25_CR24","unstructured":"Torenvliet L., Towards a strong P-Time Hierarchy, Report Uva-FVI 85-04."},{"key":"25_CR25","unstructured":"Torenvliet L, Simplicity for relativixed \u03a3 2 p , Report Uva-FVI 85-05."},{"key":"25_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"Wrathall C., Complete sets and the polynomial hierarchy, Theoretical Computer Science 3 (1976) 23\u201333.","journal-title":"Theoretical Computer Science"},{"key":"25_CR27","first-page":"1","volume":"26","author":"A. C. Yao","year":"1985","unstructured":"Yao A. C., Separating the Polynomial-Time Hierarchy by Oracles: Part I, Proc. IEEE FOCS 26 (1985) 1\u201310","journal-title":"Proc. IEEE FOCS"},{"key":"25_CR28","first-page":"392","volume":"15","author":"P. Young","year":"1983","unstructured":"Young P., Some Structural Porperties of Polynomial Reducibilities and Sets in NP, Proc. ACM SIGACT STOC 15 (1983) 392\u2013401.","journal-title":"Proc. ACM SIGACT STOC"}],"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_109.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:10:29Z","timestamp":1605643829000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_109","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}