On Percolation and NP-Hardness

الأصل · EN

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 NP-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 1-p > 0. We prove that for n-vertex graphs, these problems remain as hard as in the worst-case, as long as p > 1n¹⁻ε for arbitrary ε∈ (0,1), unless NP BPP. 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.