{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T22:00:11Z","timestamp":1718920811854},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,5,22]],"date-time":"2015-05-22T00:00:00Z","timestamp":1432252800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00037-015-0104-9","type":"journal-article","created":{"date-parts":[[2015,5,21]],"date-time":"2015-05-21T05:33:23Z","timestamp":1432186403000},"page":"533-600","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Limits on Alternation Trading Proofs for Time\u2013Space Lower Bounds"],"prefix":"10.1007","volume":"24","author":[{"given":"Samuel R.","family":"Buss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,22]]},"reference":[{"key":"104_CR1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson & Avi Wigderson (2009). Algebrization: A New Barrier in Complexity Theory. ACM Transactions on Computation Theory 1(1).","DOI":"10.1145\/1490270.1490272"},{"key":"104_CR2","doi-asserted-by":"crossref","unstructured":"Theodore Baker, John Gill & Robert Solovay (1975). Relativizations of the P=?NP Question. SIAM Journal on Computing 4, 431\u2013442.","DOI":"10.1137\/0204037"},{"key":"104_CR3","unstructured":"James Bennett (1962). On Spectra. Ph.D. thesis, Princeton University."},{"key":"104_CR4","doi-asserted-by":"crossref","unstructured":"Scott Diehl & Dieter van Melkebeek (2006). Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. SIAM Journal on Computing 36, 563\u2013594.","DOI":"10.1137\/050642228"},{"key":"104_CR5","doi-asserted-by":"crossref","unstructured":"Lance Fortnow (1997). Nondeterministic Polynomial Time Versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. In Proc. IEEE Conference on Computational Complexity (CCC), 52\u201360.","DOI":"10.1109\/CCC.1997.612300"},{"key":"104_CR6","doi-asserted-by":"crossref","unstructured":"Lance Fortnow, Richard Lipton, Dieter van Melkebeek & Anastasios Viglas (2005). Time-Space Lower Bounds for Satisfiability. Journal of the ACM 52(6), 835\u2013865.","DOI":"10.1145\/1101821.1101822"},{"key":"104_CR7","doi-asserted-by":"crossref","unstructured":"Lance Fortnow & Dieter van Melkebeek (2000). Time-Space Tradeoffs for Nondeterministic Computation. In Proc. IEEE Conference on Computational Complexity (CCC), 2\u201313.","DOI":"10.1109\/CCC.2000.856730"},{"key":"104_CR8","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01744432","volume":"17","author":"Ravi Kannan","year":"1984","unstructured":"Kannan Ravi: Towards Separating Nondeterminism from Determinism. Mathematical Systems Theory 17, 29\u201345 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"104_CR9","doi-asserted-by":"crossref","unstructured":"Richard Lipton & Anastasios Viglas (1999). On the Complexity of SAT. In Proc. 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 459\u2013464.","DOI":"10.1109\/SFFCS.1999.814618"},{"key":"104_CR10","doi-asserted-by":"crossref","unstructured":"Dieter van Melkebeek (2004). Time-Space Lower Bounds for NPComplete Problems. In Current Trends in Theoretical Computer Science, 265\u2013291. World Scientific.","DOI":"10.1142\/9789812562494_0015"},{"key":"104_CR11","doi-asserted-by":"crossref","unstructured":"Dieter van Melkebeek (2007). A Survey of Lower Bounds for Satisfiability and Related Problems. Foundations and Trends in Theoretical Computer Science 2(3), 197\u2013303.","DOI":"10.1561\/0400000012"},{"key":"104_CR12","doi-asserted-by":"crossref","unstructured":"Dieter van Melkebeek & Ran Raz (2005). A Time Lower Bound for Satisfiability. Theoretical Computer Science 348, 311\u2013320.","DOI":"10.1016\/j.tcs.2005.09.020"},{"key":"104_CR13","unstructured":"V. A. Nepomnja\u0161\u010di\u012d (1970). Rudimentary Predicates and Turing Computations. Dokl. Akad. Nauk SSSR 195, 282\u2013284. English translation in Soviet Math. Dokl. 11 (1970) 1462\u20131465."},{"key":"104_CR14","doi-asserted-by":"crossref","unstructured":"Alexander A. Razborov & Steven Rudich (1997). Natural Proofs. Journal of Computer and System Sciences 55(1), 24\u201335.","DOI":"10.1006\/jcss.1997.1494"},{"issue":"2","key":"104_CR15","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1006\/jcss.2001.1767","volume":"63","author":"Tourlakis Iannis","year":"2001","unstructured":"Iannis Tourlakis: Time-Space Tradeoffs for SAT and Related Problems. Journal of Computer and System Sciences 63(2), 268\u2013287 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"104_CR16","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/s00037-007-0221-1","volume":"15","author":"Williams Ryan","year":"2006","unstructured":"Ryan Williams: Inductive Time-Space Lower Bounds for SAT and Related Problems. Computational Complexity 15(4), 433\u2013470 (2006)","journal-title":"Computational Complexity"},{"issue":"2","key":"104_CR17","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s00037-008-0248-y","volume":"17","author":"Williams Ryan","year":"2008","unstructured":"Ryan Williams: Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Computational Complexity 17(2), 179\u2013219 (2008)","journal-title":"Computational Complexity"},{"key":"104_CR18","unstructured":"Ryan Williams (2010). Alternation-Trading Proofs, Linear Programming, and Lower Bounds. In Proc. 27th Intl. Symp. on Theory of Computings (STACS 2010), 669\u2013680."},{"key":"104_CR19","doi-asserted-by":"crossref","unstructured":"Ryan Williams (2013). Alternation-Trading Proofs, Linear Programming, and Lower Bounds. ACM Transactions of Computation Theory 5(2), article 6.","DOI":"10.1145\/2493246.2493249"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0104-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0104-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0104-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:01:59Z","timestamp":1558522919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0104-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,22]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["104"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0104-9","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,22]]}}}