{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T10:21:59Z","timestamp":1737627719497,"version":"3.33.0"},"edition-number":"1","reference-count":21,"publisher":"Wiley","isbn-type":[{"type":"print","value":"9780471383932"},{"type":"electronic","value":"9780470050118"}],"license":[{"start":{"date-parts":[[2009,3,16]],"date-time":"2009-03-16T00:00:00Z","timestamp":1237161600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This article is a brief overview of the field of computational complexity theory.<\/jats:p>","DOI":"10.1002\/9780470050118.ecse542","type":"other","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T17:49:24Z","timestamp":1196963364000},"page":"500-506","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity Theory"],"prefix":"10.1002","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2009,3,16]]},"reference":[{"key":"e_1_2_12_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602223"},{"key":"e_1_2_12_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_12_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213018"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_12_2_4_1"},{"key":"e_1_2_12_2_5_1","doi-asserted-by":"crossref","unstructured":"S.Cook The complexity of theorem proving procedures Proc. 3rd Annual ACM Symposium on Theory of Computing (STOC) 1971 pp.151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_12_2_6_1","first-page":"265","article-title":"Universal search problems","volume":"9","author":"Levin L.","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_12_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"},{"key":"e_1_2_12_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"e_1_2_12_2_8_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"e_1_2_12_2_9_1","doi-asserted-by":"crossref","unstructured":"R.ImpagliazzoandA.Wigderson P=BPP unless E has sub\u2010exponential circuits Proc. 29th ACM Symposium on Theory of Computing (STOC) 1997 pp.220\u2013229.","DOI":"10.1145\/258533.258590"},{"key":"e_1_2_12_2_10_1","doi-asserted-by":"crossref","unstructured":"O.Reingold Undirected ST\u2010connectivity in log\u2010space Proc. 37th Annual ACM Symposium on Theory of Computing (STOC) 2005 pp.376\u2013385.","DOI":"10.1145\/1060590.1060647"},{"key":"e_1_2_12_2_11_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P\u2010Completeness Theory","author":"Greenlaw R.","year":"1995"},{"key":"e_1_2_12_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"e_1_2_12_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101822"},{"key":"e_1_2_12_2_14_1","doi-asserted-by":"crossref","unstructured":"R.Williams Better time\u2010space lower bounds for SAT and related problems Proc. 20th Annual IEEE Conference on Computational Complexity (CCC) 2005 pp.40\u201349.","DOI":"10.1109\/CCC.2005.6"},{"key":"e_1_2_12_3_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032916"},{"key":"e_1_2_12_3_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04880-1"},{"key":"e_1_2_12_3_4_1","first-page":"69","volume-title":"Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity","author":"Johnson D. S.","year":"1990"},{"volume-title":"Theory of Computation","year":"2006","author":"Kozen D.","key":"e_1_2_12_3_5_1"},{"volume-title":"Computational Complexity","year":"1994","author":"Papadimitriou C.","key":"e_1_2_12_3_6_1"},{"volume-title":"Complexity Theory: Exploring the Limits of Efficient Algorithms","year":"2005","author":"Wegener I.","key":"e_1_2_12_3_7_1"}],"container-title":["Wiley Encyclopedia of Computer Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/9780470050118.ecse542","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T09:18:36Z","timestamp":1737623916000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/9780470050118.ecse542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,16]]},"ISBN":["9780471383932","9780470050118"],"references-count":21,"alternative-id":["10.1002\/9780470050118.ecse542","10.1002\/9780470050118"],"URL":"https:\/\/doi.org\/10.1002\/9780470050118.ecse542","archive":["Portico"],"relation":{},"subject":[],"published":{"date-parts":[[2009,3,16]]}}}