Closeness of NP-Hard Sets to Other Complexity Classes
Bin Fu, Hongzhou Li · SIAM Journal on Computing · 1994
Let A be a language and C be a class of languages. A is said to be s-C-close (s-C-outside-close) if there exists $B \in C$ such that $\|(A\Delta B)^{ \leqslant n} \| \leqslant s(n)$ (and $A \subseteq B$). If A is q-C-close (q-C-,outside-close) for some polynomial q then it is simply said that A is C-close (C-outside-close). The following results are shown in this paper. (1) No $NP$-hard set can be $coNP$ -close unless $NP = coNP$. (2) No $NP$-hard set can be R-close unless $NP = R$. (3) No $NP$-hard set can be $O(\log n)$-$UP$-close unless $NP = {\textit{Few}}P$. (4) No $NP$-hard set can be $O(\log n)$-$C_ = P$-close unless $NP \subseteq C_ = P$. (5) No $NP$-hard set can be $UP$-outside-close unless $NP = {\textit{Few}}P$. (6) No $NP$-hard set can be $C_ = P$-outside-close unless $NP \subseteq C_ = P$.