# If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$

The following exercise is taken from Chapter 17 of Languages and Machines by Thomas Sudkamp:

Let $$Q$$ be a language reducible to a language $$L$$ in polynomial time. Prove that $$\overline{Q}$$ is reducible to $$\overline{L}$$ in polynomial time.

I am not sure if my solution idea is correct. Anyone knows the correct solution of this exercise?

My idea is: I use the definition of NP-complete. Q is in NP class and L is NP-complete. The function f to reducible in polynomial time Q to L, is also the function f to reducible in polynomial time notQ to notL

• Could you tell us your solution idea, and why you're not sure it's correct? – Yuval Filmus Nov 3 '19 at 16:44
• I use the definition of NP-complete. Q is in NP class and L is NP-complete. The function f to reducible in polynomial time Q to L, is also the function f to reducible in polynomial time notQ to notL. – Gianni Spear Nov 3 '19 at 16:49
• This seems completely fine. Perhaps you can add such an answer to your question. – Yuval Filmus Nov 3 '19 at 16:50
• Thanks. updated my question – Gianni Spear Nov 3 '19 at 16:52
• Wait.. In the question I see no assumption that $Q \in \textrm{NP}$ or that $L$ is $\textrm{NP}$-complete. In fact those assumptions are unnecessary. – Steven Nov 3 '19 at 17:20

By hypothesis $$Q \le_p L$$, i.e., there exists a poly-time computable function $$f(x)$$ such that $$x \in L \iff f(x) \in Q$$. Then: $$x \in \overline{L} \iff x \not\in L \iff f(x) \not\in Q \iff f(x) \in \overline{Q}.$$
Therefore $$\overline{L} \le_p \overline{Q}$$.