2
$\begingroup$

If a language L is NP-complete, with respect to polynomial time reducibility, does L ≤ co-L in polynomial time?

1 Answers 1

4

Ultimately it depends on whether NP=co-NP or not. As $L$ is NP-complete, $\bar{L}$ is co-NP-complete (and more relevantly, in co-NP). If there were a polynomial time reduction such that $L \leq_{p} \bar{L}$, then $L$ would be in co-NP and hence NP $\subseteq$ co-NP (in fact you can also use it to show co-NP $\subseteq$ NP, and hence equality).

Of course we don't know if NP=co-NP, the general consensus seems to be that they're different, but you never know - and if P=NP, then we automatically get NP=co-NP (but not vice versa).