{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:51:52Z","timestamp":1725565912915},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228493"},{"type":"electronic","value":"9783540278368"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_81","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"971-982","source":"Crossref","is-referenced-by-count":2,"title":["A Time Lower Bound for Satisfiability"],"prefix":"10.1007","author":[{"given":"Dieter","family":"van Melkebeek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"81_CR1","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0020-0190(88)90152-4","volume":"26","author":"S. Cook","year":"1988","unstructured":"Cook, S.: Short propositional formulas represent nondeterministic computations. IPL\u00a026, 269\u2013270 (1988)","journal-title":"IPL"},{"key":"81_CR2","first-page":"371","volume":"8","author":"M. Dietzfelbinger","year":"1999","unstructured":"Dietzfelbinger, M., H\u00fchne, M.: Matching upper and lower bounds for simulations of several tapes on one multidimensional tape. CC\u00a08, 371\u2013392 (1999)","journal-title":"CC"},{"key":"81_CR3","first-page":"337","volume":"60","author":"L. Fortnow","year":"2000","unstructured":"Fortnow, L.: Time-space tradeoffs for satisfiability. JCSS\u00a060, 337\u2013353 (2000)","journal-title":"JCSS"},{"key":"81_CR4","first-page":"2","volume-title":"CCC","author":"L. Fortnow","year":"2000","unstructured":"Fortnow, L., van Melkebeek, D.: Time-space tradeoffs for nondeterministic computation. In: CCC, pp. 2\u201313. IEEE, Los Alamitos (2000)"},{"key":"81_CR5","first-page":"344","volume-title":"STOC","author":"R. Kannan","year":"1983","unstructured":"Kannan, R.: Alternation and the power of nondeterminism. In: STOC, pp. 344\u2013346. ACM, New York (1983)"},{"key":"81_CR6","first-page":"459","volume-title":"FOCS","author":"R. Lipton","year":"1999","unstructured":"Lipton, R., Viglas, A.: On the complexity of SAT. In: FOCS, pp. 459\u2013464. IEEE, Los Alamitos (1999)"},{"key":"81_CR7","first-page":"392","volume":"3","author":"W. Maass","year":"1993","unstructured":"Maass, W., Schnitger, G., Szemeredi, E., Turan, G.: Two tapes versus one for off-line Turing machines. CC\u00a03, 392\u2013401 (1993)","journal-title":"CC"},{"key":"81_CR8","first-page":"1462","volume":"11","author":"V. Nepomnja\u0161\u010di\u012d","year":"1970","unstructured":"Nepomnja\u0161\u010di\u012d, V.: Rudimentary predicates and Turing calculations. Doklady 11, 1462\u20131465 (1970)","journal-title":"Doklady"},{"key":"81_CR9","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"Seiferas, J., Fischer, M., Meyer, A.: Separating nondeterministic time complexity classes. JACM\u00a025, 146\u2013167 (1978)","journal-title":"JACM"},{"key":"81_CR10","first-page":"57","volume":"73","author":"D. Melkebeek van","year":"2001","unstructured":"van Melkebeek, D.: Time-space lower bounds for satisfiability. BEATCS\u00a073, 57\u201377 (2001)","journal-title":"BEATCS"},{"key":"81_CR11","volume-title":"Computational Complexity","author":"K. Wagner","year":"1986","unstructured":"Wagner, K., Wechsung, G.: Computational Complexity. Reidel Publishing, Dordrecht (1986)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_81","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:31:28Z","timestamp":1553095888000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_81"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_81","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}