{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T03:40:58Z","timestamp":1777347658684,"version":"3.51.4"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n            We prove, under a computational complexity hypothesis, that it is consistent with the true universal theory of p-time algorithms that a specific p-time function extending\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            bits to\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            bits violates the dual weak pigeonhole principle: Every string\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            equals the value of the function for some\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . The function is the truth-table function assigning to a circuit the table of the function it computes and the hypothesis is that every language in P has circuits of a fixed polynomial size\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            .\n          <\/jats:p>","DOI":"10.1145\/3446207","type":"journal-article","created":{"date-parts":[[2021,5,15]],"date-time":"2021-05-15T19:27:02Z","timestamp":1621106822000},"page":"1-4","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Small Circuits and Dual Weak PHP in the Universal Theory of p-time Algorithms"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0670-3957","authenticated-orcid":false,"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Physics, Charles University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,5,15]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Samuel R. Buss. 1986. Bounded Arithmetic. Bibliopolis Naples.  Samuel R. Buss. 1986. Bounded Arithmetic. Bibliopolis Naples."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 7th ACM Symposium on Theory of Computing (STOC\u201975)","author":"Cook Steve A.","year":"1975","unstructured":"Steve A. Cook . 1975 . Feasibly constructive proofs and the propositional calculus . In Proceedings of the 7th ACM Symposium on Theory of Computing (STOC\u201975) . ACM Press, 83\u201397. Steve A. Cook. 1975. Feasibly constructive proofs and the propositional calculus. In Proceedings of the 7th ACM Symposium on Theory of Computing (STOC\u201975). ACM Press, 83\u201397."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.12.003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1191333850"},{"key":"e_1_2_1_6_1","volume-title":"Boolean Function Complexity","author":"Jukna Statys","unstructured":"Statys Jukna . 2012. Boolean Function Complexity . Springer . Statys Jukna. 2012. Boolean Function Complexity. Springer."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90382-5"},{"key":"e_1_2_1_8_1","volume-title":"Propositional Logic, and Complexity Theory (Encyclopedia of Mathematics and Its Applications","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek . 1995. Bounded Arithmetic , Propositional Logic, and Complexity Theory (Encyclopedia of Mathematics and Its Applications , Vol. 60). Cambridge University Press. Jan Kraj\u00ed\u010dek. 1995. Bounded Arithmetic, Propositional Logic, and Complexity Theory (Encyclopedia of Mathematics and Its Applications, Vol. 60). Cambridge University Press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm170-1-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1080938841"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm182-2-7"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 13th International Congress on Logic, Methodology and Philosophy of Science. Studies in Logic and the Foundations of Mathematics","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek . 2009. A proof complexity generator . In Proceedings of the 13th International Congress on Logic, Methodology and Philosophy of Science. Studies in Logic and the Foundations of Mathematics , C. Glymour, W. Wang, and D. Westerstahl (Eds.). King\u2019s College Publications , London , 185\u2013190. Jan Kraj\u00ed\u010dek. 2009. A proof complexity generator. In Proceedings of the 13th International Congress on Logic, Methodology and Philosophy of Science. Studies in Logic and the Foundations of Mathematics, C. Glymour, W. Wang, and D. Westerstahl (Eds.). King\u2019s College Publications, London, 185\u2013190."},{"key":"e_1_2_1_13_1","unstructured":"Jan Kraj\u00ed\u010dek. 2019. Proof Complexity (Encyclopedia of Mathematics and Its Applications Vol. 170). Cambridge University Press.  Jan Kraj\u00ed\u010dek. 2019. Proof Complexity (Encyclopedia of Mathematics and Its Applications Vol. 170). Cambridge University Press."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200028061"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446207","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:04Z","timestamp":1750193224000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,30]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3446207"],"URL":"https:\/\/doi.org\/10.1145\/3446207","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,30]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}