{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T07:18:30Z","timestamp":1764314310227,"version":"3.46.0"},"reference-count":38,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","funder":[{"name":"PROOFS and the Severo Ochoa and Mara de Maeztu Program for Centers and Units of Excellence in R&D","award":["PID2019-109137GB-C22"],"award-info":[{"award-number":["PID2019-109137GB-C22"]}]},{"name":"Spanish State Research","award":["CEX2020-001084-M"],"award-info":[{"award-number":["CEX2020-001084-M"]}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"crossref","award":["578919"],"award-info":[{"award-number":["578919"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Math. Log."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory [Formula: see text] is consistent with the conjecture that [Formula: see text], i.e. some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. The same techniques establish the same results with [Formula: see text] replaced by the class of problems decidable in non-deterministic barely superpolynomial time such as [Formula: see text]. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds.<\/jats:p>","DOI":"10.1142\/s0219061324500235","type":"journal-article","created":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T04:38:42Z","timestamp":1724387922000},"source":"Crossref","is-referenced-by-count":0,"title":["On the consistency of circuit lower bounds for non-deterministic time"],"prefix":"10.1142","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3732-1989","authenticated-orcid":false,"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, i Centre de Recerca Matem\u00e0tica, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3837-334X","authenticated-orcid":false,"given":"Sam","family":"Buss","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6983-5493","authenticated-orcid":false,"given":"Moritz","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Passau, Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"S0219061324500235BIB001","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21951"},{"key":"S0219061324500235BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585253"},{"key":"S0219061324500235BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-014-0398-3"},{"key":"S0219061324500235BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129733"},{"key":"S0219061324500235BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/2559950"},{"volume-title":"Bounded Arithmetic","year":"1986","author":"Buss S. R.","key":"S0219061324500235BIB006"},{"key":"S0219061324500235BIB007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2015-06233-3"},{"issue":"2","key":"S0219061324500235BIB008","first-page":"12:1","volume":"16","author":"Byd\u017eovsk\u00fd J.","year":"2020","journal-title":"Log. Methods Comput. Sci."},{"key":"S0219061324500235BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-019-00681-y"},{"key":"S0219061324500235BIB010","first-page":"770","volume-title":"Proc. 62nd IEEE Symp. Foundations of Computer Science (FOCS)","author":"Carmosino M.","year":"2021"},{"key":"S0219061324500235BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/3538391"},{"key":"S0219061324500235BIB012","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350791"},{"key":"S0219061324500235BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"S0219061324500235BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"S0219061324500235BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.12.003"},{"key":"S0219061324500235BIB017","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1191333850"},{"key":"S0219061324500235BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90382-5"},{"key":"S0219061324500235BIB019","first-page":"191","volume":"28","author":"Karp R. M.","year":"1982","journal-title":"Enseign. Math."},{"key":"S0219061324500235BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2010.12.002"},{"key":"S0219061324500235BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90023-U"},{"key":"S0219061324500235BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2822-6_11"},{"key":"S0219061324500235BIB023","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"volume-title":"Forcing with Random Variables and Proof Complexity","year":"2011","author":"Kraj\u00ed\u010dek J.","key":"S0219061324500235BIB024"},{"issue":"1","key":"S0219061324500235BIB025","volume":"13","author":"Kraj\u00ed\u010dek J.","year":"2017","journal-title":"Log. Methods Comput. Sci."},{"key":"S0219061324500235BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2020.102930"},{"key":"S0219061324500235BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102735"},{"key":"S0219061324500235BIB028","doi-asserted-by":"publisher","DOI":"10.1137\/18M1195887"},{"key":"S0219061324500235BIB029","first-page":"65","volume-title":"Proc. 59th IEEE Symp. Foundations of Computer Science (FOCS)","author":"Oliveira I. C.","year":"2018"},{"key":"S0219061324500235BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.08.004"},{"issue":"2","key":"S0219061324500235BIB031","first-page":"1","volume":"11","author":"Pich J.","year":"2015","journal-title":"Log. Methods Comput. Sci."},{"key":"S0219061324500235BIB032","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451117"},{"key":"S0219061324500235BIB033","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"S0219061324500235BIB034","first-page":"201","volume":"59","author":"Razborov A. A.","year":"1995","journal-title":"Izv. Russ. Acad. Sci."},{"key":"S0219061324500235BIB035","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.181.2.1"},{"key":"S0219061324500235BIB037","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-014-0087-y"},{"key":"S0219061324500235BIB038","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(88)90046-2"},{"key":"S0219061324500235BIB039","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"S0219061324500235BIB040","doi-asserted-by":"publisher","DOI":"10.1137\/130938219"}],"container-title":["Journal of Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219061324500235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T07:14:45Z","timestamp":1764314085000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0219061324500235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"references-count":38,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1142\/S0219061324500235"],"URL":"https:\/\/doi.org\/10.1142\/s0219061324500235","relation":{},"ISSN":["0219-0613","1793-6691"],"issn-type":[{"type":"print","value":"0219-0613"},{"type":"electronic","value":"1793-6691"}],"subject":[],"published":{"date-parts":[[2024,9,19]]},"article-number":"2450023"}}