Exhaustive enumeration unveils clustering and freezing in the random 3-satisfiability problem

Area of Science:

• Computational complexity theory
• Statistical physics of disordered systems

Background:

• Random 3-satisfiability (3-SAT) is a canonical NP-complete problem.
• Understanding the structure of its solution space is key to explaining computational hardness.

Purpose of the Study:

• To investigate the geometrical properties of the solution space in random 3-SAT.
• To identify and characterize the phase transitions within this solution space.

Main Methods:

• Analysis of the complete set of solutions for random 3-SAT instances.
• Comparison of observed cluster numbers with theoretical asymptotic predictions.
• Localization of the freezing transition in the solution space.

Main Results:

• The number of solution clusters aligns well with theoretical predictions, even at moderate system sizes.
• A freezing transition has been identified in the solution space.
• This transition is potentially linked to the onset of computational hardness.

Conclusions:

• The geometrical structure of random 3-SAT solutions exhibits predictable clustering.
• The identified freezing transition provides insights into the computational complexity of random constraint satisfaction problems.