{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:55:50Z","timestamp":1757627750848,"version":"3.44.0"},"reference-count":46,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1990,3,1]],"date-time":"1990-03-01T00:00:00Z","timestamp":636249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1990,3,1]],"date-time":"1990-03-01T00:00:00Z","timestamp":636249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2004,5,19]],"date-time":"2004-05-19T00:00:00Z","timestamp":1084924800000},"content-version":"vor","delay-in-days":5193,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1990,3]]},"DOI":"10.1016\/0304-3975(90)90191-j","type":"journal-article","created":{"date-parts":[[2002,10,10]],"date-time":"2002-10-10T17:44:32Z","timestamp":1034271872000},"page":"79-93","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":9,"title":["New developments in structural complexity theory"],"prefix":"10.1016","volume":"71","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"year":"1987","series-title":"Bounded Queries to SAT and the Boolean Hierarchy","author":"Beigel","key":"10.1016\/0304-3975(90)90191-J_BIB1"},{"key":"10.1016\/0304-3975(90)90191-J_BIB2","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","article-title":"Relativizations of the P \u225f NP question","volume":"4","author":"Baker","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(90)90191-J_BIB3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","article-title":"On isomorphisms and density of NP and other complete sets","volume":"6","author":"Berman","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(90)90191-J_BIB4","series-title":"Technical Report, TR 85\u2013724","article-title":"The Boolean hierarchy: hardware over NP","author":"Cai","year":"1985"},{"key":"10.1016\/0304-3975(90)90191-J_BIB5","series-title":"Structure in Complexity Theory","first-page":"105","article-title":"The Boolean hierarchy: hardware over NP","volume":"223","author":"Cai","year":"1986"},{"key":"10.1016\/0304-3975(90)90191-J_BIB6","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","article-title":"The Boolean hierarchy I: Structural properties","volume":"17","author":"Cai","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(90)90191-J_BIB7","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1137\/0218007","article-title":"The Boolean hierarchy II: Applications","volume":"18","author":"Cai","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(90)90191-J_BIB8","first-page":"390","article-title":"Three results on the polynomial isomorphism of complete sets","author":"Goldsmith","year":"1986","journal-title":"Proc. IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(90)90191-J_BIB9","first-page":"115","article-title":"The structural complexity column: A retrospective on structural complexity","volume":"31","author":"Hartmanis","year":"1987","journal-title":"EATCS Bull."},{"key":"10.1016\/0304-3975(90)90191-J_BIB10","first-page":"73","article-title":"The structural complexity column: Sparse complete sets for NP and the optimal collapse of the polynomial hierarchy","volume":"32","author":"Hartmanis","year":"1987","journal-title":"EATCS Bull."},{"key":"10.1016\/0304-3975(90)90191-J_BIB11","first-page":"26","article-title":"The structural complexity column: The collapsing hierarchies","volume":"33","author":"Hartmanis","year":"1987","journal-title":"EATCS Bull."},{"key":"10.1016\/0304-3975(90)90191-J_BIB12","first-page":"40","article-title":"Solvable problems with conflicting relativizations","volume":"27","author":"Hartmanis","year":"1985","journal-title":"EATCS Bull."},{"key":"10.1016\/0304-3975(90)90191-J_BIB13","series-title":"Fundamentals of Computational Theory","first-page":"185","article-title":"Some observations about NP complete sets","volume":"278","author":"Hartmanis","year":"1987"},{"key":"10.1016\/0304-3975(90)90191-J_BIB14","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations, in: Proc. 24th Ann. Symp. on Foundations of Computer Science, IEEE Computer Society, 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"10.1016\/0304-3975(90)90191-J_BIB15","first-page":"82","article-title":"The structural complexity column: Some observations about relativization of space bounded computations","volume":"35","author":"Hartmanis","year":"1988","journal-title":"EATCS Bull."},{"key":"10.1016\/0304-3975(90)90191-J_BIB16","first-page":"110","article-title":"The strong exponential hierarchy collapses","author":"Hemachandra","year":"1987","journal-title":"ACM Symp. of Theory of Computing"},{"key":"10.1016\/0304-3975(90)90191-J_BIB17","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0019-9958(85)80004-8","article-title":"Sparse sets in NP-P: EXPTIME versus NEXPTIME","volume":"65","author":"Hartmanis","year":"1985","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(90)90191-J_BIB18","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1038\/scientificamerican0584-86","article-title":"Turing machines","author":"Hopcroft","year":"1984","journal-title":"Sci. Am."},{"year":"1979","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","key":"10.1016\/0304-3975(90)90191-J_BIB19"},{"key":"10.1016\/0304-3975(90)90191-J_BIB20","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","article-title":"Computation times of NP sets of different densities","volume":"34","author":"Hartmanis","year":"1984","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(90)90191-J_BIB21","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","article-title":"Nondeterministic space is closed under complement","volume":"17","author":"Immerman","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(90)90191-J_BIB22","first-page":"33","article-title":"PNP[log n] and sparse Turing complete sets for NP","author":"Kadin","year":"1987","journal-title":"Proc. 2nd Structure in Complexity Theory Conference"},{"key":"10.1016\/0304-3975(90)90191-J_BIB23","series-title":"Ph.D. Thesis","article-title":"Restricted Turing reducibilities and the structure of the polynomial time hierarchy","author":"Kadin","year":"1988"},{"key":"10.1016\/0304-3975(90)90191-J_BIB24","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1137\/0217080","article-title":"The polynomial hierarchy collapses if the Boolean hierarchy collapses","volume":"17","author":"Kadin","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(90)90191-J_BIB25","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0020-0190(87)90087-1","article-title":"Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE[log n] \u2260 NSPACE[log n]","volume":"25","author":"Kirsig","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(90)90191-J_BIB26","first-page":"302","article-title":"Some connections between nonuniform and uniform complexity classes","author":"Karp","year":"1980","journal-title":"ACM Symp. Theory of Computing"},{"key":"10.1016\/0304-3975(90)90191-J_BIB27","first-page":"380","article-title":"Collapsing degrees","author":"Kurtz","year":"1986","journal-title":"Proc. IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(90)90191-J_BIB28","series-title":"Proc. Automata, Languages, and Programming (ICALP 1987)","first-page":"529","article-title":"The logarithmic alternation hierarchy collapses: A \u03a3l2 = A \u03a0L2","volume":"267","author":"Lange","year":"1987"},{"key":"10.1016\/0304-3975(90)90191-J_BIB29","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/0022-0000(82)90050-2","article-title":"A note on sparse oracles for NP","volume":"24","author":"Long","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(90)90191-J_BIB30","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","article-title":"Relativization of questions about log space computability","volume":"10","author":"Ladner","year":"1976","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0304-3975(90)90191-J_BIB31","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","article-title":"Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis","volume":"25","author":"Mahaney","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(90)90191-J_BIB32","series-title":"Studies in Complexity Theory","first-page":"63","article-title":"Sparse sets and reducibilities","author":"Mahaney","year":"1986"},{"year":"1987","series-title":"Proc. Structure in Complexity Theory","key":"10.1016\/0304-3975(90)90191-J_BIB33"},{"key":"10.1016\/0304-3975(90)90191-J_BIB34","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0304-3975(85)90139-2","article-title":"Reductions among polynomial isomorphism types","volume":"39","author":"Mahaney","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(90)90191-J_BIB35","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1137\/0210057","article-title":"Limitations on separating nondeterministic complexity classes","volume":"10","author":"Rackoff","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(90)90191-J_BIB36","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","article-title":"Space-bounded hierarchies and probabilistic computations","volume":"28","author":"Ruzzo","year":"1984","journal-title":"J. Comput. System. Sci."},{"key":"10.1016\/0304-3975(90)90191-J_BIB37","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","article-title":"Relationships between nondeterministic and deterministic tape complexities","volume":"4","author":"Savitch","year":"1970","journal-title":"J. Comput. System Sci."},{"year":"1986","series-title":"Proc. Structure in Complexity Theory","key":"10.1016\/0304-3975(90)90191-J_BIB38"},{"key":"10.1016\/0304-3975(90)90191-J_BIB39","series-title":"Ph.D. Thesis","article-title":"On some subrecursive reducibilities","author":"Simon","year":"1977"},{"key":"10.1016\/0304-3975(90)90191-J_BIB40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1977","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(90)90191-J_BIB41","series-title":"STACS '88","first-page":"91","article-title":"Collapsing oracle hierarchies, census functions, and logarithmically many queries","volume":"294","author":"Schoening","year":"1988"},{"key":"10.1016\/0304-3975(90)90191-J_BIB42","first-page":"96","article-title":"The method of forcing for nondeterministic automata","volume":"33","author":"Szelepesenyi","year":"1987","journal-title":"Bull. EATCS"},{"journal-title":"\u03a32 SPACE(n) is closed under complement","year":"1987","author":"Toda","key":"10.1016\/0304-3975(90)90191-J_BIB43"},{"key":"10.1016\/0304-3975(90)90191-J_BIB44","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","article-title":"Relativized circuit complexity","volume":"31","author":"Wilson","year":"1985","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(90)90191-J_BIB45","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","article-title":"Complete sets and the polynomial-time hierarchy","volume":"3","author":"Wrathall","year":"1977","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(90)90191-J_BIB46","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","article-title":"Some consequences of non-uniform conditions on uniform classes","volume":"26","author":"Yap","year":"1983","journal-title":"Theoret. Comput. Sci."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759090191J?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759090191J?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T04:18:49Z","timestamp":1757477929000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759090191J"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,3]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,3]]}},"alternative-id":["030439759090191J"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(90)90191-j","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[1990,3]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"New developments in structural complexity theory","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0304-3975(90)90191-J","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1990 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}