We study several properties of sets that are complete for NP.
We prove that if L is an NP-complete set and S \not\supseteq L is a p-selective sparse set, then L - S is many-one-hard for NP. We demonstrate existence of a sparse set S \in \mathrm{DTIME}(2^{2^{n}})
such ... more >>>