{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:42:57Z","timestamp":1725745377675},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403125"},{"type":"electronic","value":"9783642403132"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_1","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T10:36:43Z","timestamp":1376649403000},"page":"1-7","source":"Crossref","is-referenced-by-count":0,"title":["Alternation Trading Proofs and Their Limitations"],"prefix":"10.1007","author":[{"given":"Sam","family":"Buss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"unstructured":"Bennett, J.: On Spectra. Ph.D. thesis, Princeton University (1962)","key":"1_CR1"},{"doi-asserted-by":"crossref","unstructured":"Buss, S., Williams, R.: Limits on alternation-trading proofs for time-space lower bounds, manuscript, submitted for publication. Shorter version appeared in IEEE Conf. on Computational Complexity (CCC), pp. 181\u2013191 (2012)","key":"1_CR2","DOI":"10.1109\/CCC.2012.30"},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0020-0190(88)90152-4","volume":"26","author":"S.A. Cook","year":"1988","unstructured":"Cook, S.A.: Short propositional formulas represent nondeterministic computations. Information Processing Letters\u00a026, 269\u2013270 (1988)","journal-title":"Information Processing Letters"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/050642228","volume":"36","author":"S. Diehl","year":"2006","unstructured":"Diehl, S., van Melkebeek, D.: Time-space lower bounds for the polynomial-time hierarchy on randomized machines. SIAM Journal on Computing\u00a036, 563\u2013594 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/978-3-642-02882-3_43","volume-title":"Computing and Combinatorics","author":"S. Diehl","year":"2009","unstructured":"Diehl, S., van Melkebeek, D., Williams, R.: An improved time-space lower bound for tautologies. Journal of Combinatorial Optimization 22(3), 325\u2013338 (2011), an earlier version appeared in: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol.\u00a05609, pp. 429\u2013438. Springer, Heidelberg (2009)"},{"unstructured":"Fortnow, L.: Nondeterministic polynomial time versus nondeterministic logarithmic space: Time-space tradeoffs for satisfiability. In: Proc. IEEE Conference on Computational Complexity (CCC), pp. 52\u201360 (1997)","key":"1_CR6"},{"issue":"6","key":"1_CR7","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1145\/1101821.1101822","volume":"52","author":"L. Fortnow","year":"2005","unstructured":"Fortnow, L., Lipton, R., van Melkebeek, D., Viglas, A.: Time-space lower bounds for satisfiability. Journal of the ACM\u00a052(6), 835\u2013865 (2005)","journal-title":"Journal of the ACM"},{"unstructured":"Fortnow, L., van Melkebeek, D.: Time-space tradeoffs for nondeterministic computation. In: Proc. IEEE Conference on Computational Complexity (CCC), pp. 2\u201313 (2000)","key":"1_CR8"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-51237-3_10","volume-title":"Logic at Botik \u201989","author":"Y. Gurevich","year":"1989","unstructured":"Gurevich, Y., Shelah, S.: Nearly linear time. In: Meyer, A.R., Taitslin, M.A. (eds.) Logic at Botik 1989. LNCS, vol.\u00a0363, pp. 108\u2013118. Springer, Heidelberg (1989)"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01744432","volume":"17","author":"R. Kannan","year":"1984","unstructured":"Kannan, R.: Towards separating nondeterminism from determinism. Mathematical Systems Theory\u00a017, 29\u201345 (1984)","journal-title":"Mathematical Systems Theory"},{"unstructured":"Lipton, R., Viglas, A.: On the complexity of SAT. In: Proc. 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 459\u2013464 (1999)","key":"1_CR11"},{"doi-asserted-by":"crossref","unstructured":"van Melkebeek, D.: Time-space lower bounds for NP-complete problems. In: Current Trends in Theoretical Computer Science, pp. 265\u2013291. World Scientific (2004)","key":"1_CR12","DOI":"10.1142\/9789812562494_0015"},{"unstructured":"Nepomnja\u0161\u010di\u012d, V.A.: Rudimentary predicates and Turing computations. Dokl. Akad. Nauk SSSR 195, 282\u2013284 (1970), English translation in Soviet Math. Dokl. 11, 1462\u20131465 (1970)","key":"1_CR13"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N. Pippenger","year":"1979","unstructured":"Pippenger, N., Fisher, M.J.: Relations among complexity measures. Journal of the ACM\u00a026, 361\u2013381 (1979)","journal-title":"Journal of the ACM"},{"unstructured":"Robson, J.M.: A new proof of the NP completeness of satisfiability. In: Proc. 2nd Australian Computer Science Conference, pp. 62\u201369 (1979)","key":"1_CR15"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(91)90177-4","volume":"81","author":"J.M. Robson","year":"1991","unstructured":"Robson, J.M.: An O(T logT) reduction from RAM computations to satisfiability. Theoretical Computer Science\u00a081, 141\u2013149 (1991)","journal-title":"Theoretical Computer Science"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1145\/322047.322060","volume":"25","author":"C.P. Schnorr","year":"1978","unstructured":"Schnorr, C.P.: Satisfiability is quasilinear complete in NQL. Journal of the ACM\u00a025, 136\u2013145 (1978)","journal-title":"Journal of the ACM"},{"issue":"2","key":"1_CR18","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1006\/jcss.2001.1767","volume":"63","author":"I. Tourlakis","year":"2001","unstructured":"Tourlakis, I.: Time-space tradeoffs for SAT and related problems. Journal of Computer and System Sciences\u00a063(2), 268\u2013287 (2001)","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"Williams, R.: Alternation-trading proofs, linear programming, and lower bounds, to appear. A shorter extended abstract appeared in Proc. 27th Intl. Symp. on Theory of Computings (STACS 2010) (2010), \n                  \n                    http:\/\/stacs-conf.org\n                  \n                  \n                , doi: 10.4230\/LIPIcs.STACS.2010.2494","key":"1_CR19"},{"unstructured":"Williams, R.: Algorithms and Resource Requirements for Fundamental Problems. Ph.D. thesis, Carnegie Mellon University (August 2007)","key":"1_CR20"},{"issue":"2","key":"1_CR21","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00037-008-0248-y","volume":"17","author":"R. Williams","year":"2008","unstructured":"Williams, R.: Time-space tradeoffs for counting NP solutions modulo integers. Computational Complexity\u00a017(2), 179\u2013219 (2008)","journal-title":"Computational Complexity"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T22:12:04Z","timestamp":1558303924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}