{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:50Z","timestamp":1725663290751},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540528463"},{"type":"electronic","value":"9783540471646"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52846-6_73","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:43:13Z","timestamp":1330206193000},"page":"1-12","source":"Crossref","is-referenced-by-count":6,"title":["Structural complexity theory: Recent surprises"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Desh","family":"Ranjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj","family":"Rohatgi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"1_CR1","unstructured":"L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Technical Report 90-03, Department of Computer Science, University of Chicago, March 1990."},{"issue":"1","key":"1_CR2","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"C. Bennett and J. Gill. Relative to a random oracle A, PA \u2260 NPA \u2260 co-NPA with probability 1. SIAM Journal on Computing, 10(1):96\u2013113, February 1981.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"1_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. Relativizations of the P =? NP question. SIAM Journal on Computing, 4(4):431\u2013442, December 1975.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR4","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 isomorphism and density of NP and other complete sets. SIAM Journal on Computing, 6:305\u2013322, June 1977.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"J. Cai. With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy. In ACM Symposium on Theory of Computing, pages 21\u201329, 1986.","DOI":"10.1145\/12130.12133"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"J. Cai. Probability one separation of the Boolean Hierarchy. In 4th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag Lecture Notes in Computer Science # 247, pages 148\u2013158, 1987.","DOI":"10.1007\/BFb0039602"},{"key":"1_CR7","unstructured":"A. Condon. Computational models of games. Technical Report 87-04-04, Department of Computer Science, University of Washington, 1987."},{"issue":"5","key":"1_CR8","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","volume":"28","author":"L. Fortnow","year":"1988","unstructured":"L. Fortnow and M. Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters, 28(5):249\u2013251, August 1988.","journal-title":"Information Processing Letters"},{"issue":"4","key":"1_CR9","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675\u2013695, December 1977.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Widgerson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings IEEE Symposium on Foundations of Computer Science, pages 174\u2013187, 1986.","DOI":"10.1109\/SFCS.1986.47"},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1090\/psapm\/038\/1020812","volume":"38","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser. Interactive proof systems. In Computational Complexity Theory, Proceedings of Symposia in Applied Mathematics, Volume 38, pages 108\u2013128. American Mathematical Society, 1989.","journal-title":"Computational Complexity Theory"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In ACM Symposium on Theory of Computing, pages 59\u201368, 1986.","DOI":"10.1145\/12130.12137"},{"key":"1_CR13","first-page":"40","volume":"27","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis. Solvable problems with conflicting relativizations. Bulletin of the European Association for Theoretical Computer Science, 27:40\u201349, Oct 1985.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"J. E. Hopcroft. Turing machines. Scientific American, pages 86\u201398, May 1984.","DOI":"10.1038\/scientificamerican0584-86"},{"issue":"6","key":"1_CR15","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0217080","volume":"17","author":"J. Kadin","year":"1988","unstructured":"J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses. SIAM Journal on Computing, 17(6):1263\u20131282, December 1988.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In ACM Symposium on Theory of Computing, pages 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"S. A. Kurtz, S. R. Mahaney, and J. S. Royer. The isomorphism conjecture fails relative to a random oracle. In ACM Symposium on Theory of Computing, pages 157\u2013166, 1989.","DOI":"10.1145\/73007.73022"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"K. Ko. Relativized polynomial time hierarchies having exactly k levels. In ACM Symposium on Theory of Computing, pages 245\u2013253, 1988.","DOI":"10.1145\/62212.62235"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"S. A. Kurtz. On the random oracle hypothesis. In ACM Symposium on Theory of Computing, pages 224\u2013230, 1982.","DOI":"10.1145\/800070.802195"},{"key":"1_CR20","unstructured":"C. Lund, L. Fortnow, H. Karloff, and N. Nisan. The polynomial-time hierarchy has interactive proofs. Unpublished manuscript, 1989."},{"issue":"2","key":"1_CR21","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"S. Mahaney. Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences, 25(2):130\u2013143, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou. Games against nature. In Proceedings IEEE Symposium on Foundations of Computer Science, pages 446\u2013450, 1983.","DOI":"10.1109\/SFCS.1983.20"},{"key":"1_CR23","unstructured":"A. Shamir. IP = PSPACE. Unpublished manuscript, 1989."},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"A. C. Yao. Separating the polynomial-time hierarchy by oracles. In Proceedings IEEE Symposium on Foundations of Computer Science, pages 1\u201310, 1985.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","SWAT 90"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52846-6_73.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:18Z","timestamp":1605648318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52846-6_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540528463","9783540471646"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-52846-6_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}