Relaxation and metastability in a local search procedure for the random satisfiability problem

Area of Science:

• Computational complexity
• Boolean satisfiability problems
• Local search algorithms

Background:

• RandomWalkSAT is a local search algorithm used for Boolean satisfiability problems.
• The efficiency of such algorithms can depend on the ratio of constraints to variables.

Purpose of the Study:

• To analyze the average performance of RandomWalkSAT for random Boolean constraints.
• To understand how solution time scales with problem size and constraint ratio.

Main Methods:

• Analysis of average-case properties of RandomWalkSAT.
• Systematic expansion scheme using a quantum formulation of the evolution operator.
• Annealed calculation of barrier height for metastable states.

Main Results:

• Solution time scales linearly with problem size N for low constraint ratios (alpha < alpha(d)).
• Solution time scales exponentially with N for high constraint ratios (alpha > alpha(d)).
• A polynomial to exponential crossover is observed at alpha(d) ≈ 2.7, distinct from solution clustering at alpha ≈ 3.86.

Conclusions:

• The study characterizes the computational complexity of RandomWalkSAT.
• Identifies distinct scaling regimes based on the constraint-to-variable ratio.
• Provides insights into the mechanisms of solution finding and state transitions in constraint satisfaction.