The Boolean Satisfiability problem (3-SAT) is the
canonical NP-complete benchmark in theoretical computer sci-
ence, with difficulty peaking near a critical clause-to-variable
ratio of αc ≈ 4.267, where satisfying assignments become
exponentially rare. This paper evaluates five meta-heuristic algo-
rithms across this transition: Steepest-Ascent Hill Climbing, Sim-
ulated Annealing, an Adaptive Clause-Aware Genetic Algorithm
(ACGA), an Enhanced WalkSAT Memetic Algorithm, and an
Optimized Binary Particle Swarm Optimizer, each extended with
problem-specific enhancements (ratio-aware temperature cali-
bration, clause-guided crossover, probSAT-based memetic repair,
and clause-weighted ring-topology search, respectively). A shared
incremental delta scoring scheme reduces per-flip evaluation from
O(m) to O(α · 3), yielding up to 166× speedup at n = 500.
Across fifteen instances spanning three difficulty regimes (α ∈
{3, 4.3, 6}) and five variable sizes (n ∈ {50, . . . , 500}), WalkSAT
MA achieves the strongest results, satisfying 99.58% of clauses at
the phase transition and 98.47% in the overconstrained regime.
Notably, all five algorithms converge to the same quality ceiling at
n = 500, α = 4.3, empirically confirming theoretical predictions
that the phase transition fragments the solution space into
isolated clusters unreachable by single-flip local search within
practical budgets.

Conference Title

An-Najah 1st Conference for AI Applications

Conference Country

Palestine

Conference Date

Oct. 18, 2026 - Oct. 18, 2026

Conference Sponsor

An-Najah National University

Additional Info

Conference Website