{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:01Z","timestamp":1742617141557,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578116"},{"type":"electronic","value":"9783540483373"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57811-0_1","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:23:33Z","timestamp":1330262613000},"page":"1-11","source":"Crossref","is-referenced-by-count":0,"title":["On the intellectual terrain around NP"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suresh","family":"Chari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes and systems of linear equations. In Proceedings of the 34 th IEEE Symposium on Foundations of Computer Science, pages 724\u2013733, 1993.","key":"1_CR1","DOI":"10.1109\/SFCS.1993.366815"},{"doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. In Proceedings of the 33 rd IEEE Symposium on Foundations of Computer Science, pages 14\u201323, 1992.","key":"1_CR2","DOI":"10.1109\/SFCS.1992.267823"},{"doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs. In Proceedings of the 33 rd IEEE Symposium on Foundations of Computer Science, pages 2\u201313, 1992.","key":"1_CR3","DOI":"10.1109\/SFCS.1992.267824"},{"doi-asserted-by":"crossref","unstructured":"L. Babai. Trading group theory for randomness. In Proceedings of the 17 th Annual ACM Symposium on Theory of Computing, pages 421\u2013429, 1985.","key":"1_CR4","DOI":"10.1145\/22145.22192"},{"doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. In Proceedings of the 31 st IEEE Symposium on Foundations of Computer Science, pages 16\u201325, 1990.","key":"1_CR5","DOI":"10.1109\/FSCS.1990.89520"},{"doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23 rd Annual ACM Symposium on Theory of Computing, pages 21\u201331, 1991.","key":"1_CR6","DOI":"10.1145\/103418.103428"},{"key":"1_CR7","doi-asserted-by":"crossref","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, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"34","author":"L. Babai","year":"1988","unstructured":"L. Babai and S. Moran. Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences, 34:254\u2013276, 1988.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"M. Ben-or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi prover interactive proofs: How to remove intractability. In Proceedings of the 20 th Annual ACM Symposium on Theory of Computing, pages 113\u2013131, 1988.","key":"1_CR9","DOI":"10.1145\/62212.62223"},{"doi-asserted-by":"crossref","unstructured":"S. Cook. The complexity of theorem proving procedures. In Proceedings of the 3 rd Annual ACM Symposium on Theory of Computing, pages 151\u2013158, 1971.","key":"1_CR10","DOI":"10.1145\/800157.805047"},{"doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Approximating clique is alomst NP-complete. In Proceedings of the 32 nd IEEE Symposium on Foundations of Computer Science, pages 2\u201312, 1991.","key":"1_CR11","DOI":"10.1109\/SFCS.1991.185341"},{"doi-asserted-by":"crossref","unstructured":"L. Fortnow, J. Rompel, and M. Sipser. On the power of multi-prover interactive protocols. In Proceedings of the 3 rd Structure in Complexity Theory Conference, pages 156\u2013161, 1988.","key":"1_CR12","DOI":"10.1109\/SCT.1988.5275"},{"issue":"5","key":"1_CR13","doi-asserted-by":"crossref","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, 1988.","journal-title":"Information Processing Letters"},{"key":"1_CR14","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01700692","volume":"38","author":"K. G\u00f6del","year":"1931","unstructured":"K. G\u00f6del. \u00dcber formal unentscheidbare S\u00e4tze der Principiua mathematica und verwandter Systeme. Monatshefte f\u00fcr Mathematik und Physik, 38:173\u2013198, 1931.","journal-title":"Monatshefte f\u00fcr Mathematik und Physik"},{"unstructured":"M. Garey and D. Johnson. Computers and Intractability:A guide to the theory of NP-Completeness. Freeman, 1979.","key":"1_CR15"},{"key":"1_CR16","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, and C. Rackoff. The Knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18:186\u2013208, 1989.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27 th IEEE Symposium on Foundations of Computer Science, pages 174\u2013187, 1986.","key":"1_CR17","DOI":"10.1109\/SFCS.1986.47"},{"key":"1_CR18","first-page":"101","volume":"38","author":"J. Hartmanis","year":"1989","unstructured":"J. Hartmanis. G\u00f6del, von Neumann and the P=?NP problem. Bulletin of the EATCS, 38:101\u2013107, June 1989.","journal-title":"Bulletin of the EATCS"},{"key":"1_CR19","first-page":"166","volume":"41","author":"J. Hartmanis","year":"1990","unstructured":"J. Hartmanis, R. Chang, D. Ranjan, and P. Rohatgi. On IP=PSPACE and theorems with narrow proofs. Bulletin of the EATCS, 41:166\u2013174, June 1990.","journal-title":"Bulletin of the EATCS"},{"key":"1_CR20","first-page":"1","volume":"#447","author":"J. Hartmanis","year":"1990","unstructured":"J. Hartmanis, R. Chang, D. Ranjan, and P. Rohatgi. Structural Complexity Theory: Recent Surprises. In Proceedings of SWAT 90, pages 1\u201312. Lecture Notes in Computer Science #447, 1990.","journal-title":"Lecture Notes in Computer Science"},{"doi-asserted-by":"crossref","unstructured":"J. Hartmanis, P. Lewis, and R. Stearns. Hierarchies of memory limited computations. In Proceedings of 6 th IEEE Symposium on Switching Circuit Theory and Logical Design, pages 179\u2013190, 1965.","key":"1_CR21","DOI":"10.1109\/FOCS.1965.11"},{"key":"1_CR22","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis and R. Stearns. On the computational complexity of algorithms. Trans. AMS, 117:285\u2013306, 1965.","journal-title":"Trans. AMS"},{"doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive and computational complexity. In J. Hartmanis, editor, Proceedings of Symposia in Applied Mathematics, pages 75\u201391. AMS, 1989.","key":"1_CR23","DOI":"10.1090\/psapm\/038\/1020810"},{"issue":"6","key":"1_CR24","doi-asserted-by":"crossref","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, 1988.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, 1972.","key":"1_CR25","DOI":"10.1007\/978-1-4684-2001-2_9"},{"unstructured":"L. Levin. Universal'nyie perebornyie zadachi(universal search problems). Problemy Peredachi Informatsii, 9(3), 1973.","key":"1_CR26"},{"doi-asserted-by":"crossref","unstructured":"C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 2\u201310, 1990.","key":"1_CR27","DOI":"10.1109\/FSCS.1990.89518"},{"doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. In Proceedings of the 25 th Annual ACM Symposium on Theory of Computing, pages 286\u2013293, 1993.","key":"1_CR28","DOI":"10.1145\/167088.167172"},{"issue":"2","key":"1_CR29","doi-asserted-by":"crossref","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"},{"doi-asserted-by":"crossref","unstructured":"M. Ogiwara and O. Watanabe. On poynomial time bounded truth-table reducibility of NP to sparse sets. In Proceedings of the 22 nd Annual ACM Symposium on Theory of Computing, pages 457\u2013467, 1990.","key":"1_CR30","DOI":"10.1145\/100216.100276"},{"doi-asserted-by":"crossref","unstructured":"P. Rohatgi. Saving queries with randomness. In Proceedings of the 7th Structure in Complexity Theory Conference, pages 71\u201383, 1992.","key":"1_CR31","DOI":"10.1109\/SCT.1992.215382"},{"unstructured":"P. Rohatgi. On Properties of Random Reductions. PhD thesis, Cornell University, 1994. Available as Computer Science Department technical report TR 93-1386.","key":"1_CR32"},{"unstructured":"A. Shamir. IP = PSPACE. In Proceedings of the 31 st IEEE Symposium on Foundations of Computer Science, pages 11\u201315, 1990.","key":"1_CR33"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57811-0_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:13:49Z","timestamp":1742595229000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57811-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578116","9783540483373"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-57811-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}