Tossing Coins with an š©š«-Machine
Edgar Graham Daylight Ā· Symmetry Ā· 2025
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 Ļ, defined as Ļ=Ļcellā§Ļrest. The component Ļcell enforces the constraint that each cell in the tableau contains exactly one symbol, while Ļrest incorporates constraints governing the step-by-step behavior of N on w. In recent work, we reformulated a critical part of Ļrest 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ācommonly expected by complexity specialistsāis provided. Accordingly, any claim regarding P vs. NP remains beyond the scope of this work.