The theory postulating that the algorithmic
hardness of the K-SAT problem is linked with the satisfiability phase transition however appears inconsistent with the later
rigorous discoveries obtained specifically for large values of \(K\) .
In particular, while \(\alpha _{\rm SAT}\)  is known to be approximately \(2^K\log 2\)  for large
values of \(K\) , all of the
known algorithms stall long before that,
and specifically at \(\alpha _{\rm ALG}=(2^K/K)\log K\)  [1]}. Furthermore, there is an evidence
that breaking this barrier might be extremely challenging. This was argued by proving
that the model undergoes the so-called clustering
phase transition near \(\alpha _{\rm ALG}\)  [2]},[3]}
(more on this below), but and also by ruling out various families of algorithms. These algorithms include
sequential local algorithms and algorithms based on low-degree polynomials (using the Overlap Gap Property
discussed in the next section) [4]},[5]},
the Survey Propagation algorithm [6]},
and a variant of a random search algorithm called WalkSAT [7]}.
The Survey Propagation algorithm is a highly effective heuristics for finding
satisfying assignments in random K-SAT and many other similar problems.
It is particularly effective for low values of \(K\)  and
beats many other existing approaches in terms of the running times
and sizes of instances it is capable
to handle [8]} (see also [9]} for the perspective on the approach).
It is entirely possible that this algorithm and even its more elementary
version, the Belief Propagation guided decimation algorithm solves the satisfiability problem for small
values of \(K\) . An evidence of this can be found in [10]}, and rigorous analysis
of this algorithm was conducted by Coja-Oghlan in [11]}, which shows it to be effective
when \(\alpha \le 2^K/K\) .
However, the analysis by Hetterich in [6]} rules out the Survey Propagation
algorithm for sufficiently large values of \(K\) , beyond the \(\alpha _{\rm ALG}\)  threshold, which
we recall is \((2^K/K)\log K\) .
Additionally, the theory
of algorithmic hardness based on the existence of the satisfiability
type phase transition does not appear to explain the algorithmic hardness
associated with optimization problems,
such as the largest clique problem in \(\mathbb {G}(N,1/2)\) .
