{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:56:46Z","timestamp":1742925406128,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642328930"},{"type":"electronic","value":"9783642328947"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32894-7_2","type":"book-chapter","created":{"date-parts":[[2012,9,1]],"date-time":"2012-09-01T21:33:10Z","timestamp":1346535190000},"page":"2-9","source":"Crossref","is-referenced-by-count":2,"title":["Inductive Complexity of P versus NP Problem"],"prefix":"10.1007","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Calude","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Melissa S.","family":"Queen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","volume-title":"Super-recursive Algorithms","author":"M. Burgin","year":"2005","unstructured":"Burgin, M.: Super-recursive Algorithms. Springer, Heidelberg (2005)"},{"key":"2_CR2","first-page":"11","volume":"416","author":"M. Burgin","year":"2011","unstructured":"Burgin, M., Calude, C.S., Calude, E.: Inductive Complexity Measures for Mathematical Problems. CDMTCS Research Report\u00a0416, 11 (2011)","journal-title":"CDMTCS Research Report"},{"issue":"3","key":"2_CR3","doi-asserted-by":"crossref","first-page":"267","DOI":"10.25088\/ComplexSystems.18.3.267","volume":"18","author":"C.S. Calude","year":"2009","unstructured":"Calude, C.S., Calude, E.: Evaluating the complexity of mathematical problems. Part 1. Complex Systems\u00a018(3), 267\u2013285 (2009)","journal-title":"Complex Systems"},{"issue":"4","key":"2_CR4","doi-asserted-by":"crossref","first-page":"387","DOI":"10.25088\/ComplexSystems.18.4.387","volume":"18","author":"C.S. Calude","year":"2010","unstructured":"Calude, C.S., Calude, E.: Evaluating the complexity of mathematical problems. Part 2. Complex Systems\u00a018(4), 387\u2013401 (2010)","journal-title":"Complex Systems"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1112\/S1461157009000461","volume":"13","author":"C.S. Calude","year":"2010","unstructured":"Calude, C.S., Calude, E.: The complexity of the Four Colour Theorem. LMS J. Comput. Math.\u00a013, 414\u2013425 (2010)","journal-title":"LMS J. Comput. Math."},{"key":"2_CR6","first-page":"12","volume":"410","author":"C.S. Calude","year":"2011","unstructured":"Calude, C.S., Calude, E.: The Complexity of Mathematical Problems: An Overview of Results and Open Problems. CDMTCS Research Report\u00a0410, 12 (2011)","journal-title":"CDMTCS Research Report"},{"key":"2_CR7","first-page":"285","volume":"12","author":"C.S. Calude","year":"2006","unstructured":"Calude, C.S., Calude, E., Dinneen, M.J.: A new measure of the difficulty of problems. Journal for Multiple-Valued Logic and Soft Computing\u00a012, 285\u2013307 (2006)","journal-title":"Journal for Multiple-Valued Logic and Soft Computing"},{"key":"2_CR8","unstructured":"Calude, C.S., Calude, E., Queen, M.S.: The complexity of Euler\u2019s integer partition theorem. Theoretical Computer Science (2012), doi:10.1016.\/j.tcs.2012.03.02"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1063\/1.3489096","volume":"20","author":"C.S. Calude","year":"2010","unstructured":"Calude, C.S., Calude, E., Svozil, K.: The complexity of proving chaoticity and the Church-Turing Thesis. Chaos\u00a020, 037103, 1\u20135 (2010)","journal-title":"Chaos"},{"key":"2_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04978-5","volume-title":"Information and Randomness: An Algorithmic Perspective","author":"C.S. Calude","year":"2002","unstructured":"Calude, C.S.: Information and Randomness: An Algorithmic Perspective, 2nd edn. Springer, Berlin (2002) (revised and extended)","edition":"2"},{"issue":"3-4","key":"2_CR11","first-page":"257","volume":"18","author":"E. Calude","year":"2012","unstructured":"Calude, E.: The complexity of Riemann\u2019s Hypothesis. Journal for Multiple-Valued Logic and Soft Computing\u00a018(3-4), 257\u2013265 (2012)","journal-title":"Journal for Multiple-Valued Logic and Soft Computing"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1145\/800157.805047","volume-title":"STOC 1971, Proceedings of the Third Annual ACM Symposium on Theory of Computing","author":"S. Cook","year":"1971","unstructured":"Cook, S.: The complexity of theorem proving procedures. In: STOC 1971, Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM, New York (1971)"},{"key":"2_CR13","unstructured":"Cook, S.: The P versus NP Problem, 12 pages (manuscript), \n                      http:\/\/www.claymath.org\/millennium\/P_vs_NP\/pvsnp.pdf\n                     (visited on June 16, 2012)"},{"key":"2_CR14","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill (2001) [1990]"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-642-27654-5_7","volume-title":"Computation, Physics and Beyond","author":"M.J. Dinneen","year":"2012","unstructured":"Dinneen, M.J.: A Program-Size Complexity Measure for Mathematical Problems and Conjectures. In: Dinneen, M.J., Khoussainov, B., Nies, A. (eds.) Computation, Physics and Beyond. LNCS, vol.\u00a07160, pp. 81\u201393. Springer, Heidelberg (2012)"},{"issue":"9","key":"2_CR16","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/1562164.1562186","volume":"52","author":"L. Fortnow","year":"2009","unstructured":"Fortnow, L.: The status of the P vs NP problem. CACM\u00a052(9), 78\u201386 (2009)","journal-title":"CACM"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. JACM\u00a021, 277\u2013292 (1974)","journal-title":"JACM"},{"issue":"5","key":"2_CR18","first-page":"560","volume":"55","author":"A. Jackson","year":"2008","unstructured":"Jackson, A.: Interview with Martin Davis. Notices AMS\u00a055(5), 560\u2013571 (2008)","journal-title":"Notices AMS"},{"key":"2_CR19","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"Levin, L.: Universal search problems. Problemy Peredachi Informatsii\u00a09, 265\u2013266 (1973) (in Russian), English translation in [22]","journal-title":"Problemy Peredachi Informatsii"},{"key":"2_CR20","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001","volume-title":"The Nature of Computation","author":"C. Moore","year":"2011","unstructured":"Moore, C., Mertens, S.: The Nature of Computation. Oxford University Press, Oxford (2011)"},{"issue":"6","key":"2_CR21","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/2184319.2184341","volume":"55","author":"K.D. Mulmuley","year":"2012","unstructured":"Mulmuley, K.D.: The GCT program toward the P vs NP problem. CACM\u00a055(6), 98\u2013107 (2012)","journal-title":"CACM"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/MAHC.1984.10036","volume":"6","author":"B.A. Trakhtenbrot","year":"1984","unstructured":"Trakhtenbrot, B.A.: A survey of Russian approaches to Perebor (brute-force search) algorithms. Annals of the History of Computing\u00a06, 384\u2013400 (1984)","journal-title":"Annals of the History of Computing"},{"key":"2_CR23","unstructured":"http:\/\/www.claymath.org\/millennium\/P_vs_NP\/\n                     (visited on June 16, 2012)"},{"key":"2_CR24","unstructured":"http:\/\/www.claymath.org\/millennium\/Riemann_Hypothesis\/\n                     (visited on June 16, 2012)"},{"key":"2_CR25","unstructured":"W\u00f6ginger, G.J.: The P-versus-NP webpage, \n                      http:\/\/www.win.tue.nl\/~gwoegi\/P-versus-NP.htm\n                     (visited on June 16, 2012)"}],"container-title":["Lecture Notes in Computer Science","Unconventional Computation and Natural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32894-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T06:24:45Z","timestamp":1674109485000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-32894-7_2"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642328930","9783642328947"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32894-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}