{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T00:19:17Z","timestamp":1760660357006,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T00:00:00Z","timestamp":1760572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>In computational complexity, a tableau represents a hypothetical accepting computation path p of a nondeterministic polynomial time Turing machine N on an input w. The tableau is encoded by the formula \u03c8, defined as \u03c8=\u03c8cell\u2227\u03c8rest. The component \u03c8cell enforces the constraint that each cell in the tableau contains exactly one symbol, while \u03c8rest incorporates constraints governing the step-by-step behavior of N on w. In recent work, we reformulated a critical part of \u03c8rest as a compact Horn formula. In another paper, we evaluated the cost of this reformulation, though our estimates were intentionally conservative. Here, we provide a more rigorous analysis and derive a polynomial bound for two enhanced variants of our original Filling Holes with Backtracking algorithm: the refined (rFHB) and streamlined (sFHB) versions, each tasked with solving 3-SAT. The improvements stem from exploiting inter-cell dependencies spanning large regions of the tableau in the case of rFHB, and by incorporating correlated coin-tossing constraints in the case of sFHB. These improvements are purely conceptual; no empirical validation\u2014commonly expected by complexity specialists\u2014is provided. Accordingly, any claim regarding P vs. NP remains beyond the scope of this work.<\/jats:p>","DOI":"10.3390\/sym17101745","type":"journal-article","created":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T12:17:02Z","timestamp":1760617022000},"page":"1745","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tossing Coins with an \ud835\udca9\ud835\udcab-Machine"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9815-3966","authenticated-orcid":false,"given":"Edgar Graham","family":"Daylight","sequence":"first","affiliation":[{"name":"a.k.a. Karel Van Oudheusden, Department of Computer Science, KU Leuven, Celestijnenlaan 200a, Box 2402, 3001 Leuven, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Daylight, E.G. (2025). Tableau with Holes: Clarifying NP-Completeness. Symmetry, 17.","DOI":"10.3390\/sym17050677"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Daylight, E. (2025). Injecting Observers into Computational Complexity. Philosophies, 10.","DOI":"10.3390\/philosophies10040076"},{"key":"ref_3","unstructured":"Dean, W. (2025, August 01). Computational Complexity Theory. The Stanford Encyclopedia of Philosophy, Available online: https:\/\/plato.stanford.edu\/archives\/fall2021\/entries\/computational-complexity."},{"key":"ref_4","unstructured":"Fortnow, L. (2025, July 01). Why Can\u2019t We Break Cryptography. Available online: https:\/\/blog.computationalcomplexity.org\/2025\/04\/why-cant-we-break-crytptography.html."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Li, M., and Vitanyi, P. (2019). An Introduction to Kolmogorov Complexity and Its Applications, Springer. [4th ed.]. Texts in Computer Science.","DOI":"10.1007\/978-3-030-11298-1"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.1016\/j.ipl.2009.06.013","article-title":"Time-Bounded Incompressibility of Compressible Strings and Sequences","volume":"109","author":"Daylight","year":"2009","journal-title":"Inf. Process. Lett."},{"key":"ref_7","unstructured":"Cook, S. (1971, January 3\u20135). The Complexity of Theorem-Proving Procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, Shaker Heights, OH, USA."},{"key":"ref_8","first-page":"265","article-title":"Universal Sorting Problems","volume":"9","author":"Levin","year":"1973","journal-title":"Probl. Inf. Transm."},{"key":"ref_9","first-page":"95","article-title":"A Short History of Computational Complexity","volume":"80","author":"Fortnow","year":"2003","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"ref_10","unstructured":"Sipser, M. (2006). Introduction to the Theory of Computation, Thomson Course Technology."},{"key":"ref_11","unstructured":"Papadimitriou, C. (1994). Computational Complexity, Addison Wesley Longman."},{"key":"ref_12","unstructured":"Hopcroft, J., Motwani, R., and Ullman, J. (2007). Introduction to Automata Theory, Languages, and Computation, Addison Wesley\/Pearson Education."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Aaronson, S. (2013). Quantum Computing Since Democritus, Cambridge University Press.","DOI":"10.1017\/CBO9780511979309"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Horsten, L., and Welch, P. (2016). Algorithms and the Mathematical Foundations of Computer Science. G\u00f6del\u2019s Disjunction, Oxford University Press. [1st ed.].","DOI":"10.1093\/acprof:oso\/9780198759591.001.0001"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Tall, D. (2013). How Humans Learn to Think Mathematically: Exploring the Three Worlds of Mathematics, Cambridge University Press.","DOI":"10.1017\/CBO9781139565202"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Turner, R. (2021). Computational Abstraction. Entropy, 23.","DOI":"10.3390\/e23020213"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1111\/nous.12208","article-title":"Actual and Potential Infinity","volume":"53","author":"Linnebo","year":"2019","journal-title":"No\u00fbs"},{"key":"ref_18","unstructured":"Fortnow, L. (2024, August 22). Can You Feel the Machine?. Available online: https:\/\/blog.computationalcomplexity.org\/2024\/03\/can-you-feel-machine.html."},{"key":"ref_19","unstructured":"Hill, R.K. (2024, August 22). The Imperativity of Algorithms. Available online: https:\/\/cacm.acm.org\/blogcacm\/the-imperativity-of-algorithms\/."},{"key":"ref_20","unstructured":"Gr\u00e4del, E. (2009). Complexity Theory: WS 2009\/10, Mathematische Grundlagen der Informatik."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","article-title":"Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae","volume":"1","author":"Dowling","year":"1984","journal-title":"J. Log. Program."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1756","DOI":"10.1093\/comjnl\/bxr002","article-title":"Dijkstra\u2019s Rallying Cry for Generalization: The Advent of the Recursive Procedure, late 1950s\u2013early 1960s","volume":"54","author":"Daylight","year":"2011","journal-title":"Comput. J."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1305\/ndjfl\/1093883561","article-title":"Acceptable notation","volume":"23","author":"Shapiro","year":"1982","journal-title":"Notre Dame J. Form. Log."},{"key":"ref_24","unstructured":"Daylight, E., and Schuettpelz, E. (2025, August 01). The Turing Machine as a Boundary Object: Sorting Out American Science and European Engineering. Available online: https:\/\/www.youtube.com\/watch?v=Fssz-LbRcTI."},{"key":"ref_25","unstructured":"Grattan-Guinness, I. (1970). The Development of the Foundations of Mathematical Analysis from Euler to Riemann, MIT Press."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/10\/1745\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T13:06:13Z","timestamp":1760619973000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/10\/1745"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,16]]},"references-count":25,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["sym17101745"],"URL":"https:\/\/doi.org\/10.3390\/sym17101745","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,16]]}}}