On Percolation and $NP$-Hardness

Daniel Reichman, Igor Shinkar

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$-h…