{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T10:27:37Z","timestamp":1648636057117},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p> This paper does not propose a solution, not even a new possible attack, to the P versus NP problem. We are asking the simpler question: How \u201ccomplex\u201d is the P versus NP problem? Using the inductive complexity measure\u2014a measure based on computations run by inductive register machines of various orders\u2014developed in [2], we determine an upper bound on the inductive complexity of second order of the P versus NP problem. From this point of view, the P versus NP problem is significantly more complex than the Riemann hypothesis. To date, the P versus NP problem and the Goostein theorem (which is unprovable in Peano Arithmetic) are the most complex mathematical statements (theorems, conjectures and problems) studied in this framework [9, 5, 6, 2, 20]. <\/jats:p>","DOI":"10.1142\/s0129626413500072","type":"journal-article","created":{"date-parts":[[2013,3,28]],"date-time":"2013-03-28T06:58:05Z","timestamp":1364453885000},"page":"1350007","source":"Crossref","is-referenced-by-count":2,"title":["INDUCTIVE COMPLEXITY OF THE P VERSUS NP PROBLEM"],"prefix":"10.1142","volume":"23","author":[{"given":"CRISTIAN S.","family":"CALUDE","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Auckland, Auckland, New Zealand"},{"name":"Isaac Newton Institute for Mathematical Sciences, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ELENA","family":"CALUDE","sequence":"additional","affiliation":[{"name":"Institute of Natural and Mathematical Sciences, Massey University at Auckland, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MELISSA S.","family":"QUEEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Auckland, Auckland, New Zealand"},{"name":"Dartmouth College, New Hampshire, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,3,27]]},"reference":[{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157009000461"},{"key":"p_9","first-page":"285","volume":"12","author":"Calude C. S.","year":"2006","journal-title":"Journal for Multiple-Valued Logic and Soft Computing"},{"key":"p_12","first-page":"1","volume":"20","author":"Calude C. S.","journal-title":"Chaos"},{"issue":"3","key":"p_13","first-page":"257","volume":"18","author":"Calude E.","year":"2012","journal-title":"Journal for Multiple-Valued Logic and Soft Computing"},{"key":"p_18","first-page":"9","volume":"52","author":"Fortnow L.","year":"2009","journal-title":"CACM"},{"key":"p_20","first-page":"7445","volume":"2012","author":"Hertel J.","year":"2012","journal-title":"Proceedings UCNC"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"p_22","first-page":"5","volume":"55","author":"Jackson A.","year":"2008","journal-title":"Notices AMS"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-009-9402-6"},{"key":"p_24","first-page":"265","volume":"9","author":"Levin L.","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184341"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626413500072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:37:04Z","timestamp":1565181424000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626413500072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":12,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2013,3,27]]},"published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1142\/S0129626413500072"],"URL":"https:\/\/doi.org\/10.1142\/s0129626413500072","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3]]}}}