{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:17:50Z","timestamp":1725664670539},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602460"},{"type":"electronic","value":"9783540447689"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60246-1_114","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:56:50Z","timestamp":1330261010000},"page":"82-92","source":"Crossref","is-referenced-by-count":0,"title":["On the computing paradigm and computational complexity"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"266","author":"L. M. Adleman","year":"1994","unstructured":"Adleman, Leonard M.: Molecular Computation of Solutions of Combinatorial Problems. Science 266 (Nov. 1994) 1021\u20131024","journal-title":"Science"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. ACM Symposium on Theory of Computing, (1985) 421\u2013429","DOI":"10.1145\/22145.22192"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L. and Hartmanis, J.: On isomorphism and density of NP and other complete sets. SIAM Journal on Computing 6 (1977) 305\u2013322","journal-title":"SIAM Journal on Computing"},{"issue":"No.1","key":"6_CR4","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"Bennett, C. and J. Gill: Relative to a Random Oracle A, P A \u2260 NP A \u2260 co-NP A with probability 1. SIAM J. Comput. 10 No. 1 (1981) 96\u2013113","journal-title":"SIAM J. Comput."},{"key":"6_CR5","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/S0022-0000(05)80084-4","volume":"49","author":"C. Richard","year":"1994","unstructured":"Chang, Richard, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan and Pankaj Rohatgi: The Random Oracle Hypothesis is False. J. Computer and System Sciences 49 (August 1994) 24\u201339","journal-title":"J. Computer and System Sciences"},{"key":"6_CR6","first-page":"96","volume":"A400","author":"D. Deutsch","year":"1985","unstructured":"Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Roy. Soc. Lond. A400 (1985) 96\u2013117","journal-title":"Proc. Roy. Soc. Lond."},{"key":"6_CR7","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"A39","author":"D. Deutsch","year":"1992","unstructured":"Deutsch, D. and Jozsa, R.: Rapid solution of problems by quantum computation. Proc. Roy. Soc. Lond. A39 (1992) 553\u2013558","journal-title":"Proc. Roy. Soc. Lond."},{"issue":"No.6\/7","key":"6_CR8","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R. Feymnan","year":"1982","unstructured":"Feymnan, R.: Simulating physics with computers. International Journal of Theoretical Physics 21 No. 6\/7 (1982) 467\u2013488","journal-title":"International Journal of Theoretical Physics"},{"key":"6_CR9","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/BF01886518","volume":"16","author":"R. Feynman","year":"1986","unstructured":"Feynman, R.: Quantum mechanical computers. Foundations of Physics 16 (1986) 507\u2013531 (Originally appeared in Optics News, Feb. 1985)","journal-title":"Foundations of Physics"},{"key":"6_CR10","unstructured":"Fenner, S. and Fortnow, and Kurtz, S.: The isomorphism conjecture holds relative to an oracle. SIAM J. Comp. to appear."},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","volume":"28","author":"L. Fortnow","year":"1988","unstructured":"Fortnow, L. and Sipser, M.: Are there interactive protocols for co-NP languages? Inform. Proc. Lett. 28 (1988) 249\u2013251","journal-title":"Inform. Proc. Lett."},{"issue":"No.1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S. Micali, S. and Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18 No. 1 (1989) 186\u2013208","journal-title":"SIAM J. Comput."},{"key":"6_CR13","first-page":"117","volume":"37","author":"J. Hartmanis","year":"1989","unstructured":"Hartmanis, J.: Structural Complexity Column: \u201cOn the Importance of Being II 2 Hard. Bulletin of the European Association of Theoretical Computer Science (EATCS) 37 (Feb. 1989) 117\u2013127","journal-title":"Bulletin of the European Association of Theoretical Computer Science (EATCS)"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Hopcroft, J. E.: Turing machines. Sci. Amer., (May 1984) 86\u201398","DOI":"10.1038\/scientificamerican0584-86"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Kurtz, S. A.: On the random oracle hypothesis. ACM Symposium on Theory of Computing, 1982. 224\u2013230","DOI":"10.1145\/800070.802195"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Kurtz, S.A. with Mahaney, S.R. and Royer, J.S.: The isomorphism conjecture fails relative to a random oracle. ACM Symposium on Theory of Computing, 1989. 157\u2013166","DOI":"10.1145\/73007.73022"},{"key":"6_CR17","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1126\/science.7725098","volume":"262","author":"R. J. Lipton","year":"1995","unstructured":"Lipton, Richard J.: DNA Solutions to Hard Computational Problems. Science 262 (April, 1995) 542\u2013545","journal-title":"Science"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Schor, Peter W.: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. \u201cProceedings 35th Annual Symposium on Foundations of Computer Science.\u201d (Nov. 1994)","DOI":"10.1109\/SFCS.1994.365700"},{"key":"6_CR19","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. Journal of the ACM 39 (1992) 869\u2013877","journal-title":"Journal of the ACM"},{"key":"6_CR20","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1126\/science.268.5210.545","volume":"262","author":"H. T. Siegelman","year":"1995","unstructured":"Siegelman, Hava T.: Computation Beyond the Turing Limit Science 262 (April, 1995) 545\u2013548","journal-title":"Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1995"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60246-1_114.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:56:27Z","timestamp":1605628587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60246-1_114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602460","9783540447689"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-60246-1_114","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}