Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
Yongjian Zhan · 2026
Read Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity by Yongjian Zhan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-23411.txt.
Description
Yongjian Zhan proposes a strictly discrete geometric model for phase shifts and hardness in random 3-SAT. Older accounts lean on physics analogies, such as replica symmetry breaking and energy maps. Those give deep large-scale insight but lack small-scale structure.
The new model maps the phenomena onto the shape math of an N-dimensional Boolean hypercube, defining the problem space through valid solutions. Rules for clustering and freezing follow from dropping vertices and Hamming-distance links. Sharp limits follow too: a lowest no-solution limit at density eight over N, with at least N(N-1)(N-2) over six no-solution cores. A highest all-solution limit sits at seven over six times (N-1)(N-2), with two to the N top cases. These extremes explain why the average-case Satisfiability Threshold Conjecture holds only 'almost surely', and the framework explains the easy-hard-easy curve via depth-first search geometry.
Catalog record
| CREATOR | Yongjian Zhan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-23411