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

CREATORYongjian Zhan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-23411

Browse the full library · About the Tower of Babel