{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T02:32:52Z","timestamp":1761964372078,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540194880"},{"type":"electronic","value":"9783540392910"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19488-6_122","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:13:35Z","timestamp":1330200815000},"page":"271-286","source":"Crossref","is-referenced-by-count":5,"title":["New developments in structural complexity theory"],"prefix":"10.1007","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"20_CR1","unstructured":"Beigel, R. \u201cBounded Queries to SAT and the Boolean Hierarchy\u201d, manuscript, June 1987."},{"issue":"4","key":"20_CR2","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, T., J. Gill, and R. Solovay. \u201cRelativizations of the P =? NP Question\u201d, SIAM Journal on Computing, 4(4):431\u2013442, December 1975.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"20_CR3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L. and J. Hartmanis. \u201cOn Isomorphisms and Density of NP and Other Complete Sets\u201d, SIAM Journal on Computing, 6(2):305\u2013322, June 1977.","journal-title":"SIAM Journal on Computing"},{"key":"20_CR4","unstructured":"Cai, J. and L. Hemachandra. \u201cThe Boolean Hierarchy: Hardware Over NP\u201d, Technical Report, TR 85-724, Cornell Department of Computer Science, December 1985."},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Cai, J. and L. Hemachandra. \u201cThe Boolean Hierarchy: Hardware Over NP\u201d, Structure in Complexity Theory, pp. 105\u2013124, Springer-Verlag Lecture Notes in Computer Science, No. 223, 1986.","DOI":"10.1007\/3-540-16486-3_93"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Goldsmith, J. and D. Joseph. \u201cThree Results on the Polynomial Isomorphism of Complete Sets\u201d, Proceedings IEEE Symposium on Foundations of Computer Science, pp. 390\u2013397, 1986.","DOI":"10.1109\/SFCS.1986.56"},{"key":"20_CR7","first-page":"115","volume":"31","author":"J. Hartmanis","year":"1987","unstructured":"Hartmanis, J. \u201cThe Structural Complexity Column: A Retrospective on Structural Complexity\u201d, EATCS Bulletin, 31:115, February 1987.","journal-title":"EATCS Bulletin"},{"key":"20_CR8","first-page":"73","volume":"32","author":"J. Hartmanis","year":"1987","unstructured":"Hartmanis, J. \u201cThe Structural Complexity Column: Sparse Complete Sets for NP and the Optimal Collapse of the Polynomial Hierarchy\u201d, EATCS Bulletin, 32:73\u201381, June 1987.","journal-title":"EATCS Bulletin"},{"key":"20_CR9","first-page":"26","volume":"33","author":"J. Hartmanis","year":"1987","unstructured":"Hartmanis, J. \u201cThe Structural Complexity Column: The Collapsing Hierarchies\u201d, EATCS Bulletin, 33:26\u201339, October 1987.","journal-title":"EATCS Bulletin"},{"key":"20_CR10","first-page":"40","volume":"27","author":"J. Hartmanis","year":"1985","unstructured":"Hartmanis, J. \u201cSolvable Problems with Conflicting Relativizations\u201d, EATCS Bulletin, 27:40\u201349, October 1985.","journal-title":"EATCS Bulletin"},{"key":"20_CR11","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-18740-5_41","volume":"278","author":"J. Hartmanis","year":"1987","unstructured":"Hartmanis, J. \u201cSome Observations about NP Complete Sets\u201d, Fundamentals of Computational Theory, Springer-Verlag Lecture Notes in Computer Science, 278:185\u2013196, 1987.","journal-title":"Fundamentals of Computational Theory, Springer-Verlag Lecture Notes in Computer Science"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Hartmanis, J. \u201cGeneralized Kolmogorov Complexity and the Structure of Feasible Computations\u201d, Proceedings 24th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Hemachandra, L. \u201cThe Strong Exponential Hierarchy Collapses\u201d, ACM Symposium of Theory of Computing, pp. 110-122, 1987.","DOI":"10.1145\/28395.28408"},{"key":"20_CR14","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"Hartmanis, J., N. Immerman, and V. Sewelson. \u201cSparse Sets in NP \u2014 P:EXPTIME Versus NEXPTIME\u201d, Information and Control, 65:159\u2013181, May\/June 1985.","journal-title":"Information and Control"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E. \u201cTuring Machines\u201d, Scientific American, pp. 86\u201398, May 1984.","DOI":"10.1038\/scientificamerican0584-86"},{"key":"20_CR16","unstructured":"Hopcroft, J. and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"key":"20_CR17","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"Hartmanis, J. and Y. Yesha. \u201cComputation Times of NP Sets of Different Densities\u201d, Theoretical Computer Science, 34:17\u201332, 1984.","journal-title":"Theoretical Computer Science"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Immerman, N. \u201cNondeterministic Space is Closed Under Complement\u201d, Yale University Technical Report, August 1987 (accepted for publication in SICOMP).","DOI":"10.1109\/SCT.1988.5270"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Kadin, J. \u201cP NP[logn] and Sparse Turing Complete Sets for NP\u201d, Proceedings 2nd Structure in Complexity Theory Conference, pp. 33\u201340, Ithaca, New York, June 1987. Submitted to Journal of Computer and Systems Sciences.","DOI":"10.1109\/PSCT.1987.10319252"},{"key":"20_CR20","unstructured":"Kadin, J. Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy. Ph.D. Thesis, Cornell University, February 1988."},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Kadin, J. \u201cThe Polynomial Hierarchy Collapses if the Boolean Hierarchy Collapses\u201d, Cornell University, Department of Computer Science Technical Report, TR 87-843, June 1987.","DOI":"10.1109\/SCT.1988.5287"},{"key":"20_CR22","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0020-0190(87)90087-1","volume":"25","author":"B. Kirsig","year":"1987","unstructured":"Kirsig, B. and K. J. Lange. \u201cSeparation with the Ruzzo, Simon, and Tompa Relativization Implies DSPACE[logn] \u2260 NSPACE[logn]\u201d Information Processing Letters, 25:13\u201315, 1987.","journal-title":"Information Processing Letters"},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Karp, R. and R. Lipton, \u201cSome Connections Between Nonuniform and Uniform Complexity Classes\u201d, ACM Symposium on Theory of Computing, pp. 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Kurtz, S., S. Mahaney, and J. Royer. \u201cCollapsing Degrees.\u201d Proceedings IEEE Symposium on Foundations of Computer Science, pp. 380\u2013389, 1986.","DOI":"10.1109\/SFCS.1986.13"},{"key":"20_CR25","first-page":"529","volume":"267","author":"K. Lange","year":"1987","unstructured":"Lange, K., B. Jenner, and B. Kirsig. \u201cThe Logarithmic Alternation Hierarchy Collapses: A \u03a3 2 L =A \u03a0 2 L \u201d, Automata, Languages, and Programming (ICALP 1987), Springer-Verlag Lecture Notes in Computer Science, 267:529\u2013541, 1987.","journal-title":"Automata, Languages, and Programming (ICALP 1987), Springer-Verlag Lecture Notes in Computer Science"},{"key":"20_CR26","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/0022-0000(82)90050-2","volume":"24","author":"T. Long","year":"1982","unstructured":"Long, T. \u201cA Note on Sparse Oracles for NP\u201d, Journal of Computer and System Sciences, 24:224\u2013232, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR27","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. E. Ladner","year":"1976","unstructured":"Ladner, R. E. and N. A. Lynch. \u201cRelativization of Questions About Log Space Computability.\u201d Mathematical Systems Theory, 10:19\u201332, 1976.","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"20_CR28","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"Mahaney, S. \u201cSparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis\u201d, Journal of Computer and System Sciences, 25(2)130\u2013143, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR29","first-page":"63","volume-title":"Studies in Complexity Theory","author":"S. Mahaney","year":"1986","unstructured":"Mahaney, S. \u201cSparse Sets and Reducibilities.\u201d Studies in Complexity Theory, ed. R.V. Book, John Wiley and Sons, Inc. New York, pp. 63\u2013118, 1986."},{"key":"20_CR30","unstructured":"Mahaney S., ed. Proceedings Structure in Complexity Theory, Second Annual Conference Computer Society Press, 1987."},{"key":"20_CR31","doi-asserted-by":"crossref","unstructured":"Mahaney, S. and P. Young. \u201cReductions Among Polynomial Isomorphism Types\u201d, Theoretical Computer Science, 207\u2013224, 1985.","DOI":"10.1016\/0304-3975(85)90139-2"},{"key":"20_CR32","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1137\/0210057","volume":"10","author":"C.W. Rackoff","year":"1981","unstructured":"Rackoff, C.W. and J. I. Seiferas. \u201cLimitations on Separating Nondeterministic Complexity Classes\u201d, SIAM Journal on Computing, 10:742\u2013745, 1981.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"20_CR33","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W.L. Ruzzo","year":"1984","unstructured":"Ruzzo, W.L., J. Simon, and M. Tompa. \u201cSpace-Bounded Hierarchies and Probabilistic Computations\u201d, Journal of Computer and Systems Sciences, 28(4):216\u2013230, November 1984.","journal-title":"Journal of Computer and Systems Sciences"},{"issue":"2","key":"20_CR34","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J. \u201cRelationships Between Nondeterministic and Deterministic Tape Complexities\u201d, Journal of Computer and Systems Sciences, 4(2):177\u2013192, 1970","journal-title":"Journal of Computer and Systems Sciences"},{"key":"20_CR35","doi-asserted-by":"crossref","unstructured":"Selman, A.L., ed. Proceedings Structure in Complexity Theory, Springer Verlag Lecture Notes in Computer Science, No. 223, 1986.","DOI":"10.1007\/3-540-16486-3"},{"key":"20_CR36","unstructured":"Simon, I. On Some Subrecursive Reducibilities. Ph.D. Thesis, Stanford University, March 1977."},{"key":"20_CR37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L. \u201cThe Polynomial-Time Hierarchy\u201d, Theoretical Computer Science, 3:1\u201322, 1977.","journal-title":"Theoretical Computer Science"},{"key":"20_CR38","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BFb0035835","volume":"294","author":"U. Schoening","year":"1988","unstructured":"Schoening, U. and K.W. Wagner. \u201cCollapsing Oracle Hierarchies, Census Functions, and Logarithmically Many Queries\u201d, STACS '88 Springer-Verlag Lecture Notes in Computer Science, 294:91\u201397, 1988.","journal-title":"STACS '88 Springer-Verlag Lecture Notes in Computer Science"},{"key":"20_CR39","first-page":"96","volume":"33","author":"R. Szelepcsenyi","year":"1987","unstructured":"Szelepcsenyi, R. \u201cThe Method of Forcing for Nondeterministic Automata\u201d, The Bulletin on the EATCS, 33:96\u2013100, October 1987.","journal-title":"The Bulletin on the EATCS"},{"key":"20_CR40","doi-asserted-by":"crossref","unstructured":"Toda, S. \u201c\u03a32 SPACE(n) is Closed Under Complement\u201d, submitted for publication, 1987.","DOI":"10.1016\/0022-0000(87)90009-2"},{"issue":"2","key":"20_CR41","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. Wilson","year":"1985","unstructured":"Wilson, C. \u201cRelativized Circuit Complexity\u201d, Journal of Computer and System Sciences, 31(2):169\u2013181, October 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR42","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"Wrathall, C. \u201cComplete Sets and the Polynomial-Time Hierarchy\u201d, Theoretical Computer Science, 3:23\u201333, 1977.","journal-title":"Theoretical Computer Science"},{"key":"20_CR43","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C. Yap","year":"1983","unstructured":"Yap, C. \u201cSome Consequences of Non-Uniform Conditions on Uniform Classes\u201d, Theoretical Computer Science, 26:287\u2013300, 1983.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19488-6_122.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:44:58Z","timestamp":1742589898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19488-6_122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194880","9783540392910"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/3-540-19488-6_122","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}