  For large clause-to-variable ratio, typical K-SAT instances drawn from the
uniform distribution have no solution. We argue, based on statistical mechanics
calculations using the replica and cavity methods, that rare satisfiable
instances from the uniform distribution are very similar to typical instances
drawn from the so-called planted distribution, where instances are chosen
uniformly between the ones that admit a given solution. It then follows, from a
recent article by Feige, Mossel and Vilenchik, that these rare instances can be
easily recognized (in O(log N) time and with probability close to 1) by a
simple message-passing algorithm.
