1
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Could you tell us your solution idea, and why you're not sure it's correct? $\endgroup$ – Yuval Filmus Nov 3 '19 at 16:44
  • $\begingroup$ 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. $\endgroup$ – Gianni Spear Nov 3 '19 at 16:49
  • $\begingroup$ This seems completely fine. Perhaps you can add such an answer to your question. $\endgroup$ – Yuval Filmus Nov 3 '19 at 16:50
  • $\begingroup$ Thanks. updated my question $\endgroup$ – Gianni Spear Nov 3 '19 at 16:52
  • $\begingroup$ 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. $\endgroup$ – Steven Nov 3 '19 at 17:20
2
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.