{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T15:40:09Z","timestamp":1735918809400,"version":"3.32.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1991,12,1]],"date-time":"1991-12-01T00:00:00Z","timestamp":691545600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1991,12]]},"DOI":"10.1007\/bf02090397","type":"journal-article","created":{"date-parts":[[2005,8,14]],"date-time":"2005-08-14T17:27:51Z","timestamp":1124040471000},"page":"179-200","source":"Crossref","is-referenced-by-count":25,"title":["Completeness for nondeterministic complexity classes"],"prefix":"10.1007","volume":"24","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Steven","family":"Homer","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02090397_CR1","volume-title":"EATCS Monographs on Theoretical Computer Science, Vol. 11","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar J. L., J. D\u00edaz, and J. Gabarr\u00f3. Structural complexity I. (W. Brauer, G, Rozenberg, and A, Salomaa, eds.). EATCS Monographs on Theoretical Computer Science, Vol. 11. Springer-Verlag, New York, 1988."},{"key":"BF02090397_CR2","doi-asserted-by":"crossref","unstructured":"Berman L. On the structure of complete sets.Proc. 17th IEEE Conference on Foundations of Computer Science, 1976, pp. 76\u201380.","DOI":"10.1109\/SFCS.1976.22"},{"key":"BF02090397_CR3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"1","author":"L. Berman","year":"1977","unstructured":"Berman L., and J. Hartmanis. On isomorphisms and density ofNP and other complete sets.SIAM J. Comput. 1 (1977), 305\u2013322.","journal-title":"SIAM J. Comput."},{"key":"BF02090397_CR4","doi-asserted-by":"crossref","unstructured":"Cook, S. A. The complexity of theorem-proving procedures.Proc. Third ACM Symposium on Theory of Computing, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"BF02090397_CR5","series-title":"Technical Report","first-page":"240","volume-title":"Complete Problems and Strong Polynomial Reducibilities","author":"K. Ganesan","year":"1989","unstructured":"Ganesan K. and S. Homer. Complete Problems and Strong Polynomial Reducibilities. Technical Report #88-001, Boston University, January 1988. Also inAspects of Computer Science. Lecture Notes in Computer Science, Vol. 349. Springer-Verlag, Berlin, 1989, pp. 240\u2013250."},{"key":"BF02090397_CR6","unstructured":"Hartmanis J.Feasible Computations and Provable Complexity Properties. NSF Regional Conference Series in Applied Mathematics, 1978."},{"key":"BF02090397_CR7","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(78)90018-X","volume":"7","author":"J. Hartmanis","year":"1978","unstructured":"Hartmanis J. On the logtape isomorphism of complete sets.Theoret. Comput. Sci. 7 (1978), 273\u2013286.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02090397_CR8","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman N. Nondeterministic space is closed under complementation.SIAM J. Comput. 17 (1988), 935\u2013938.","journal-title":"SIAM J. Comput."},{"key":"BF02090397_CR9","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"Jones N. Space bounded reducibilities among combinatorial problems.J. Comput. System Sci. 11 (1975), 68\u201385.","journal-title":"J. Comput. System Sci."},{"key":"BF02090397_CR10","doi-asserted-by":"crossref","unstructured":"Karp R. M. Reducibility among combinatorial problems. InComplexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum, New York, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"BF02090397_CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1975","unstructured":"Ladner R. and N. Lynch. Relativizations of questions about log space computability.Math. Systems Theory 10 (1975), 19\u201332.","journal-title":"Math. Systems Theory"},{"key":"BF02090397_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. E. Ladner","year":"1975","unstructured":"Ladner R. E., N. Lynch, and A. L. Selman. A comparison of polynomial time reducibilities.Theoret. Comput. Sci. 1 (1975), 103\u2013123.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02090397_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/3-540-16486-3_107","volume-title":"Optimal approximations of complete sets","author":"D. Russo","year":"1986","unstructured":"Russo D. Optimal approximations of complete sets.Proc. Structure in Complexity Theory Conference, 1986. Lecture Notes in Computer Science, Vol. 223, Springer-Verlag, Berlin, 1986, pp. 311\u2013324."},{"key":"BF02090397_CR14","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"Szelepcs\u00e9nyi R. The method of forcing for nondeterministic automata.Bull. EATCS 33 (1987), 96\u2013100.","journal-title":"Bull. EATCS"},{"key":"BF02090397_CR15","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"Watanabe O. A comparison of polynomial time completeness notions.Theoret. Comput. Sci. 54 (1987), 249\u2013265.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02090397_CR16","unstructured":"Watanabe O. On the Structure of Intractable Complexity Classes. Ph.D. thesis, Department of Computer Science, Tokyo Institute of Technology, 1987."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02090397.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02090397\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02090397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T15:15:10Z","timestamp":1735917310000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02090397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,12]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,12]]}},"alternative-id":["BF02090397"],"URL":"https:\/\/doi.org\/10.1007\/bf02090397","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"type":"print","value":"0025-5661"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[1991,12]]}}}