{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:50:54Z","timestamp":1725663054012},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_62","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:51:37Z","timestamp":1330177897000},"page":"123-135","source":"Crossref","is-referenced-by-count":10,"title":["Complexity classes without machines: On complete languages for UP"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lane","family":"Hemachandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"14_CR1","series-title":"Department of Computer Science Technical Report","volume-title":"Some Comments on Functional Self-Reducibility and the NP Hierarchy","author":"A. Borodin","year":"1976","unstructured":"A. Borodin and A. Demers. Some Comments on Functional Self-Reducibility and the NP Hierarchy. Department of Computer Science Technical Report TR76-284, July 1976. Cornell University, Ithaca, New York."},{"key":"14_CR2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich. On the Unique Satisfiability Problem. Information and Control 55 (1982), 80\u201382.","journal-title":"Information and Control"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"P. Berman. Relations Between Density and Deterministic Complexity of NP-Complete Languages. Proceedings Symposium on Mathematical Foundations of Computer Science, 1978, Springer-Verlag, 63\u201371.","DOI":"10.1007\/3-540-08860-1_6"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"J. Cai and L. Hemachandra. The Boolean Hierarchy: Hardware over NP. To appear in Proceedings of the Structure in Complexity Theory Conference, Lecture Notes in Computer Science (1986), Springer-Verlag.","DOI":"10.1007\/3-540-16486-3_93"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"S.A. Cook. The Complexity of Theorem-Proving Procedures. Proceedings ACM Symposium on Theory of Computation (1971), 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"14_CR6","doi-asserted-by":"crossref","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 (1977), 675\u2013695.","journal-title":"SIAM Journal on Computing"},{"key":"14_CR7","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., 1979."},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"J. Grollmann and A.L. Selman. Complexity Measures for Public-Key Cryptosystems. Proceedings IEEE Symposium on Foundations of Computer Science (1984), 495\u2013503.","DOI":"10.1109\/SFCS.1984.715952"},{"key":"14_CR9","first-page":"250","volume":"194","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis and N. Immerman. On Complete Problems for NP \u2229 CoNP. Automata Languages and Programming, Lecture Notes in Computer Science 194 (1985), Springer-Verlag, 250\u2013259.","journal-title":"Automata Languages and Programming, Lecture Notes in Computer Science"},{"key":"14_CR10","volume-title":"Introduction to Automata Theory, languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, languages, and Computation. Addison-Wesley, Reading, Massachusetts, 1979."},{"key":"14_CR11","unstructured":"M. Li. Lower Bounds in Computational Complexity. Ph.D. Dissertation, Cornell University, 1985."},{"key":"14_CR12","first-page":"523","volume":"140","author":"M. Sipser","year":"1982","unstructured":"M. Sipser. On Relativization and the Existence of Complete Sets. Automata, Languages and Programming, Lecture Notes in Computer Science 140 (1982), Springer-Verlag, 523\u2013531.","journal-title":"Automata, Languages and Programming, Lecture Notes in Computer Science"},{"key":"14_CR13","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. Relative Complexity of Checking and Evaluating. Information Processing Letters 5 (1976), 20\u201323.","journal-title":"Information Processing Letters"}],"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-16761-7_62.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:10:52Z","timestamp":1605625852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_62","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}