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
We analyze the pure literal rule heuristic for computing a satisfying assignment to a random 3-CNF formula with n variables. We show that the pure literal rule by itself finds satisfying assignments for almost all 3-CNF formulas with up to 1.63n clauses, but it fails for more than 1.7n clauses. As an aside we show that the value of maximum satisfiability for random 3-CNF formulas is tightly concentrated around its mean.