We consider the robustness of computational hardness of problems whose input is obtained by applying independent random deletions to worst-case instances. For some classical @math -hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary graph are deleted independently with probability @math . We prove that for @math -vertex graphs, these problems remain as hard as in the worst-case, as long as @math for arbitrary @math , unless @math . We also prove hardness results for Constraint Satisfaction Problems, where random deletions are applied to clauses or variables, as well as the Subset-Sum problem, where items of a given instance are deleted at random.
Similar reasoning applies to @math formulas. It is well known that there exists @math such that a random @math formula in which each possible clause is added independently with probability @math can be solved with high probability using the pure literal heuristic @cite_15 . As observed in @cite_15 , if this heuristic fails in finding a satisfying assignment for a formula @math it will still fail to find a satisfying assignment if clauses are added to @math . This implies that for any @math -variable @math formula @math , if @math , then the clause-percolated formula is satisfiable and furthermore a satisfying assignment can be found in polynomial time using the pure literal heuristic.
@cite_15
1963913579
Let @math be a uniformly distributed random @math -SAT formula with @math variables and @math clauses. For clauses variables ratio @math the formula @math is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond @math with a non-vanishing probability. Non-rigorous statistical mechanics work on @math -CNF led to the development of a new efficient "message passing algorithm" called [M ', Science 2002]. Experiments conducted for @math suggest that the algorithm finds satisfying assignments close to @math . However, in the present paper we prove that the basic version of Survey Propagation Guided Decimation fails to solve random @math -SAT formulas efficiently already for @math with @math almost a factor @math below @math .