  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 > \frac{1}{n^{1-\epsilon}}$
for arbitrary $\epsilon \in (0,1)$, unless $NP \subseteq 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.
