Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity

Yongjian Zhan

The structural phase transitions and computational complexity of random 3-SAT instances are traditionally described using thermodynamic analogies from statistical physics, such as…