{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T11:29:24Z","timestamp":1744284564586},"publisher-location":"Berlin\/Heidelberg","reference-count":5,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354015650X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0015750","type":"book-chapter","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T05:45:47Z","timestamp":1132724747000},"page":"250-259","source":"Crossref","is-referenced-by-count":15,"title":["On complete problems for NP\u2229CoNP"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[]},{"given":"Neil","family":"Immerman","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"Baker, T., J. Gill and R. Solovay. \u201cRelativization of the P=?NP Question\u201d. SIAM Journal of Computing (1975), 431\u2013442.","DOI":"10.1137\/0204037"},{"key":"25_CR2","volume-title":"Computers and Intractability: A guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. and D.S. Johnson. \u201cComputers and Intractability: A guide to the Theory of NP-Completeness\u201d. W.H. Freeman and Co., San Francisco, 1979."},{"key":"25_CR3","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/BFb0030318","volume":"176","author":"W. Kowalczyk","year":"1984","unstructured":"Kowalczyk, W. \u201cSome Connections Between Representability of Complexity Classes and the Power of Formal Systems of Reasoning\u201d. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 176. Springer-Verlag 1984, 364\u2013369.","journal-title":"Lecture Notes in Computer Science"},{"key":"25_CR4","volume-title":"Theory of Recursive Functions and Effective Computability","author":"J. Rogers Jr.","year":"1967","unstructured":"Rogers, J., Jr. \u201cTheory of Recursive Functions and Effective Computability\u201d. McGraw-Hill, New York, 1967."},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/BFb0012797","volume":"140","author":"M. Sipser","year":"1982","unstructured":"Sipser, M. \u201cOn Relativization and the Existence of Complete Sets\u201d. Automata Languages and Programming Lecture Notes in Computer Science 140. Springer-Verlag 1982, 523\u2013531.","journal-title":"Lecture Notes in Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0015750.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T15:09:52Z","timestamp":1607353792000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354015650X"],"references-count":5,"URL":"https:\/\/doi.org\/10.1007\/bfb0015750","relation":{},"subject":[]}}