{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:52Z","timestamp":1759637632340,"version":"3.44.0"},"reference-count":44,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1990,10,1]],"date-time":"1990-10-01T00:00:00Z","timestamp":654739200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1990,10,1]],"date-time":"1990-10-01T00:00:00Z","timestamp":654739200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:00:00Z","timestamp":1133395200000},"content-version":"vor","delay-in-days":5540,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1990,10]]},"DOI":"10.1016\/0022-0000(90)90038-m","type":"journal-article","created":{"date-parts":[[2003,12,4]],"date-time":"2003-12-04T07:01:00Z","timestamp":1070521260000},"page":"251-271","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":21,"title":["On the complexity of ranking"],"prefix":"10.1016","volume":"41","author":[{"given":"Lane A.","family":"Hemachandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven","family":"Rudich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0022-0000(90)90038-M_BIB1","series-title":"Proceedings, CRYPTO","article-title":"On generating solved instances of computational problems","author":"Abadi","year":"1988"},{"key":"10.1016\/0022-0000(90)90038-M_BIB2","series-title":"Proceedings, 19th IEEE Symposium on Foundations of Computer Science","first-page":"75","article-title":"Two theorems on random polynomial time","author":"Adleman","year":"1978"},{"article-title":"Time, Space, and Randomness","year":"1979","author":"Adleman","key":"10.1016\/0022-0000(90)90038-M_BIB3"},{"key":"10.1016\/0022-0000(90)90038-M_BIB4","series-title":"19th ACM Symposium on Theory of Computing","first-page":"462","article-title":"Recognizing primes in random polynomial time","author":"Adleman","year":"1987"},{"article-title":"Invertible Functions","year":"1985","author":"Allender","key":"10.1016\/0022-0000(90)90038-M_BIB5"},{"key":"10.1016\/0022-0000(90)90038-M_BIB6","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(80)90027-4","article-title":"On counting problems and the polynomial-time hierarchy","volume":"12","author":"Angluin","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0022-0000(90)90038-M_BIB7","series-title":"Proceedings, 21st IEEE Symposium on Foundations of Computer Science","first-page":"387","article-title":"On distinguishing prime numbers from composite numbers","author":"Adleman","year":"1980"},{"issue":"No. 6","key":"10.1016\/0022-0000(90)90038-M_BIB8","doi-asserted-by":"crossref","first-page":"1193","DOI":"10.1137\/0217075","article-title":"P-printable sets","volume":"17","author":"Allender","year":"1988","journal-title":"SIAM J. Comput."},{"issue":"No. 6","key":"10.1016\/0022-0000(90)90038-M_BIB9","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/BF00264313","article-title":"Sets with small generalized Kolmogorov complexity","volume":"23","author":"Balcazar","year":"1986","journal-title":"Acta Inform."},{"key":"10.1016\/0022-0000(90)90038-M_BIB10","series-title":"Proceedings, 25th IEEE Symposium on Foundations of Computer Science","first-page":"308","article-title":"Sparse oracles and uniform complexity classes","author":"Balcazar","year":"1984"},{"key":"10.1016\/0022-0000(90)90038-M_BIB11","series-title":"STACS 1987: 4th Annual Symposium on Theoretical Aspects of Computer Science","first-page":"169","article-title":"Computing the counting function of context-free languages","volume":"Vol. 247","author":"Bertoni","year":"1987"},{"key":"10.1016\/0022-0000(90)90038-M_BIB12","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/0890-5401(89)90063-1","article-title":"Enumerative counting is hard","volume":"92","author":"Cai","year":"1989","journal-title":"Inform. and Comput."},{"key":"10.1016\/0022-0000(90)90038-M_BIB13","series-title":"3rd ACM Symposium on Theory of Computing","first-page":"151","article-title":"The complexity of theorem-proving procedures","author":"Cook","year":"1971"},{"issue":"No. 4","key":"10.1016\/0022-0000(90)90038-M_BIB14","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","article-title":"Computational complexity of probabilistic Turing machines","volume":"6","author":"Gill","year":"1977","journal-title":"SIAM J. Comput."},{"year":"1979","series-title":"Computers and Intractability: A Guide to the Theory of NPCompleteness","author":"Garey","key":"10.1016\/0022-0000(90)90038-M_BIB15"},{"key":"10.1016\/0022-0000(90)90038-M_BIB16","series-title":"18th ACM Symposium on Theory of Computing","first-page":"316","article-title":"Almost all primes can be quickly certified","author":"Goldwasser","year":"1986"},{"key":"10.1016\/0022-0000(90)90038-M_BIB17","series-title":"17th ACM Symposium on Theory of Computing","first-page":"440","article-title":"Compression and ranking","author":"Goldberg","year":"1985"},{"key":"10.1016\/0022-0000(90)90038-M_BIB18","article-title":"Feasible Computations and Provable Complexity Properties","volume":"Vol. 30","author":"Hartmanis","year":"1978"},{"key":"10.1016\/0022-0000(90)90038-M_BIB19","series-title":"Proceedings, 2nd Structure in Complexity Theory Conference","first-page":"103","article-title":"On ranking","author":"Hemachandra","year":"1987"},{"key":"10.1016\/0022-0000(90)90038-M_BIB20","series-title":"Mathematical Foundations of Computer Science 1988, Proceedings, 13th Symposium","first-page":"59","article-title":"Structure of complexity classes: Separations, collapses, and completeness","volume":"Vol. 324","author":"Hemachandra","year":"1988"},{"key":"10.1016\/0022-0000(90)90038-M_BIB21","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","article-title":"Complexity classes without machines: On complete languages for UP","volume":"58","author":"Hartmanis","year":"1988","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0022-0000(90)90038-M_BIB22","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0020-0190(88)90176-7","article-title":"On sparse oracles separating feasible complexity classes","volume":"28","author":"Hartmanis","year":"1988","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0022-0000(90)90038-M_BIB23","series-title":"Proceedings of 14th International Symposium on Mathematical Foundations of Computer Science","first-page":"259","article-title":"Polynomial-Time Functions Generate SAT: On P-Splinters","author":"Hemachandra","year":"1989"},{"key":"10.1016\/0022-0000(90)90038-M_BIB24","series-title":"Automata, Languages, and Programming (ICALP 1985)","first-page":"250","article-title":"On complete problems for NP \u2229 coNP","volume":"Vol. 194","author":"Hartmanis","year":"1985"},{"issue":"Nos. 2\/3","key":"10.1016\/0022-0000(90)90038-M_BIB25","first-page":"159","article-title":"Sparse sets in NP-P: EXPTIME versus NEXPTIME","volume":"65","author":"Hartmanis","year":"1985","journal-title":"Inform. and Control"},{"key":"10.1016\/0022-0000(90)90038-M_BIB26","series-title":"Proceedings, 3rd Structure in Complexity Theory Conference","first-page":"204","article-title":"The complexity of ranking","author":"Huynh","year":"1988"},{"key":"10.1016\/0022-0000(90)90038-M_BIB27","series-title":"Proceedings, 11th World Computer Congress","first-page":"281","article-title":"Using randomness to characterize the complexity of computation","author":"Hemachandra","year":"1989"},{"key":"10.1016\/0022-0000(90)90038-M_BIB28","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."},{"issue":"Nos. 2, 3","key":"10.1016\/0022-0000(90)90038-M_BIB29","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","article-title":"Random generation of combinatorial structures from a uniform distribution","volume":"43","author":"Jerrum","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0022-0000(90)90038-M_BIB30","series-title":"12th ACM Sympos. on Theory of Computing","first-page":"302","article-title":"Some connections between nonuniform and uniform complexity classes","author":"Karp","year":"1980"},{"key":"10.1016\/0022-0000(90)90038-M_BIB31","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/0885-064X(85)90012-3","article-title":"Continuous optimization problems and a polynomial hierarchy of real functions","volume":"1","author":"Ko","year":"1985","journal-title":"J. Complexity"},{"key":"10.1016\/0022-0000(90)90038-M_BIB32","series-title":"20th ACM Symposium on Theory of Computing","article-title":"Relativized polynomial time hierarchies having exactly k levels","author":"Ko","year":"1988"},{"key":"10.1016\/0022-0000(90)90038-M_BIB33","series-title":"Algorithms and Complexity","article-title":"Probabilistic algorithms","author":"Rabin","year":"1976"},{"key":"10.1016\/0022-0000(90)90038-M_BIB34","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1145\/321724.321731","article-title":"Computational work and time on finite machines","volume":"19","author":"Savage","year":"1972","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0022-0000(90)90038-M_BIB35","article-title":"Complexity and Structure","volume":"Vol. 221","author":"Sch\u00f6ning","year":"1986"},{"article-title":"On Some Central Problems in Computational Complexity","year":"1975","author":"Simon","key":"10.1016\/0022-0000(90)90038-M_BIB36"},{"key":"10.1016\/0022-0000(90)90038-M_BIB37","series-title":"Automata, Languages, and Programming","article-title":"On relativization and the existence of complete sets","volume":"Vol. 140","author":"Sipser","year":"1982"},{"key":"10.1016\/0022-0000(90)90038-M_BIB38","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."},{"issue":"No. 4","key":"10.1016\/0022-0000(90)90038-M_BIB39","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1137\/0214060","article-title":"On approximation algorithms for #P","volume":"14","author":"Stockmeyer","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(90)90038-M_BIB40","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The complexity of computing the permanent","volume":"8","author":"Valiant","year":"1979","journal-title":"Theoret. Comput. Sci."},{"issue":"No. 3","key":"10.1016\/0022-0000(90)90038-M_BIB41","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","article-title":"The complexity of enumeration and reliability problems","volume":"8","author":"Valiant","year":"1979","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(90)90038-M_BIB42","series-title":"17th ACM Symposium on Theory of Computing","first-page":"458","article-title":"NP is as easy as detecting unique solutions","author":"Valiant","year":"1985"},{"key":"10.1016\/0022-0000(90)90038-M_BIB43","series-title":"Proceedings, 26th IEEE Symposium on Foundations of Computer Science","first-page":"1","article-title":"Separating the polynomial-time hierarchy by oracles","author":"Yao","year":"1985"},{"key":"10.1016\/0022-0000(90)90038-M_BIB44","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":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002200009090038M?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002200009090038M?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T18:11:16Z","timestamp":1757095876000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/002200009090038M"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,10]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,10]]}},"alternative-id":["002200009090038M"],"URL":"https:\/\/doi.org\/10.1016\/0022-0000(90)90038-m","relation":{},"ISSN":["0022-0000"],"issn-type":[{"type":"print","value":"0022-0000"}],"subject":[],"published":{"date-parts":[[1990,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On the complexity of ranking","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0022-0000(90)90038-M","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 Inc.","name":"copyright","label":"Copyright"}]}}