# Complement of NP-Complete

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

-

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).