{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:02:11Z","timestamp":1725562931270},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_40","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T16:17:45Z","timestamp":1281716265000},"page":"453-464","source":"Crossref","is-referenced-by-count":0,"title":["Improved Simulation of Nondeterministic Turing Machines"],"prefix":"10.1007","author":[{"given":"Subrahmanyam","family":"Kalyanasundaram","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard J.","family":"Lipton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth W.","family":"Regan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Farbod","family":"Shokrieh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"40_CR1","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R. Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289\n                  n\n                ). J. Algorithms\u00a054(2), 168\u2013204 (2005)","journal-title":"J. Algorithms"},{"key":"40_CR2","unstructured":"Doty, D.: An oracle a such that \n                  \n                    \n                  \n                  $\\mbox{NTIME}^{A}(t(n)) \\not\\subseteq \\mbox{DTIME}^{A}(2^{\\varepsilon t(n)})$\n                , via Kolmogorov complexity. Private Communication (2009)"},{"key":"40_CR3","unstructured":"Feige, U., Kilian, J.: On limited versus polynomial nondeterminism. Chicago J. Theoret. Comput. Sci., Article 1, 20 p. (1997) (electronic)"},{"issue":"2","key":"40_CR4","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J. Hopcroft","year":"1977","unstructured":"Hopcroft, J., Paul, W.J., Valiant, L.: On time versus space. J. Assoc. Comput. Mach.\u00a024(2), 332\u2013337 (1977)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"40_CR5","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput.\u00a07(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Kannan, R.: Towards separating nondeterministic time from deterministic time. In: 22nd Annual Symposium on Foundations of Computer Science, SFCS 1981, pp. 235\u2013243 (October 1981)","DOI":"10.1109\/SFCS.1981.51"},{"key":"40_CR7","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1145\/800061.808764","volume-title":"STOC 1983: Proceedings of the fifteenth annual ACM symposium on Theory of computing","author":"R. Kannan","year":"1983","unstructured":"Kannan, R.: Alternation and the power of nondeterminism. In: STOC 1983: Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp. 344\u2013346. ACM, New York (1983)"},{"key":"40_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-45077-1_29","volume-title":"Fundamentals of Computation Theory","author":"R.J. Lipton","year":"2003","unstructured":"Lipton, R.J., Viglas, A.: Non-uniform depth of polynomial time and space simulations. In: Lingas, A., Nilsson, B.J. (eds.) FCT 2003. LNCS, vol.\u00a02751, pp. 311\u2013320. Springer, Heidelberg (2003)"},{"issue":"2","key":"40_CR9","first-page":"415","volume":"26","author":"J. Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carolin.\u00a026(2), 415\u2013419 (1985)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"40_CR10","volume-title":"Computational complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley Publishing Company, Reading (1994)"},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Paul, W.J., Pippenger, N., Szemeredi, E., Trotter, W.T.: On determinism versus non-determinism and related problems. In: 24th Annual Symposium on Foundations of Computer Science, pp. 429\u2013438 (November 1983)","DOI":"10.1109\/SFCS.1983.39"},{"issue":"3","key":"40_CR12","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(81)90035-0","volume":"22","author":"W.J. Paul","year":"1981","unstructured":"Paul, W.J., Reischuk, R.: On time versus space. II. J. Comput. System Sci.\u00a022(3), 312\u2013327 (1981), Special issued dedicated to Michael Machtey","journal-title":"J. Comput. System Sci."},{"key":"40_CR13","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/800070.802173","volume-title":"STOC 1982: Proceedings of the fourteenth annual ACM symposium on Theory of computing","author":"N. Pippenger","year":"1982","unstructured":"Pippenger, N.: Probabilistic simulations (preliminary version). In: STOC 1982: Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 17\u201326. ACM, New York (1982)"},{"issue":"2","key":"40_CR14","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N. Pippenger","year":"1979","unstructured":"Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. Assoc. Comput. Mach.\u00a026(2), 361\u2013381 (1979)","journal-title":"J. Assoc. Comput. Mach."},{"key":"40_CR15","unstructured":"Santhanam, R.: Relationships among time and space complexity classes (2001), \n                  \n                    http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.24.5170"},{"key":"40_CR16","first-page":"328","volume-title":"20th Annual Symposium on Foundations of Computer Science","author":"R. Schroeppel","year":"1979","unstructured":"Schroeppel, R., Shamir, A.: A T\u00b7S\n                2\u2009=\u2009O(2\n                  n\n                ) time\/space tradeoff for certain NP-complete problems. In: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, pp. 328\u2013336. IEEE, New York (1979)"},{"issue":"3","key":"40_CR17","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R.E. Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput.\u00a06(3), 537\u2013546 (1977)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"40_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/S0097539703438629","volume":"35","author":"D. Melkebeek van","year":"2005","unstructured":"van Melkebeek, D., Santhanam, R.: Holographic proofs and derandomization. SIAM J. Comput.\u00a035(1), 59\u201390 (2005) (electronic)","journal-title":"SIAM J. Comput."},{"key":"40_CR19","doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: STOC 2010: Proceedings of the fortysecond annual ACM symposium on Theory of computing (to appear, 2010)","DOI":"10.1145\/1806689.1806723"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:01:43Z","timestamp":1606168903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}