If a language L is NP-complete, with respect to polynomial time reducibility, does L ≤ co-L in polynomial time?
Complement of NP-Complete
2
$\begingroup$
computational-complexity
computational-mathematics
1 Answers
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).