Behavior of heuristics on large and hard satisfiability problems.

Area of Science:

• Computer Science
• Artificial Intelligence
• Computational Complexity

Background:

• Random satisfiability problems present significant computational challenges.
• Stochastic local search heuristics are commonly used for these problems.
• Existing heuristics like WALKSAT can be complex.

Purpose of the Study:

• To introduce and analyze a new, simpler heuristic for solving random satisfiability problems.
• To evaluate the performance of the Average Satisfiability (ASAT) heuristic near the satisfiability threshold.
• To compare ASAT with existing benchmark heuristics like WALKSAT.

Main Methods:

• The study employs stochastic local search.
• The Average Satisfiability (ASAT) heuristic is utilized, featuring a "focused" update strategy.
• Performance is analyzed for random K-satisfiability problems, particularly for K=3.

Main Results:

• ASAT solves random 3-satisfiability instances up to N=10^6 in average linear time.
• The heuristic is effective up to a clause-to-variable ratio of 4.21.
• For K>3, ASAT solves instances up to the full replica symmetry breaking (FSRB) threshold in linear time.

Conclusions:

• ASAT is a highly efficient and simpler heuristic for solving large-scale random satisfiability problems.
• The focused update strategy contributes to ASAT's performance near the satisfiability threshold.
• ASAT offers a competitive alternative to more complex heuristics for various K-satisfiability instances.