1
$\begingroup$

I found this statement in a true/false test section: enter image description here

Could someone explain in laymans why this is a true statement?

My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must be $\operatorname{co-\mathcal{NP}}$-hard. However, here we are assuming that a language that is $\operatorname{co-\mathcal{NP}}$-hard ($\overline X$) is reduceable to an $\mathcal{NP}$-complete language (3SAT). This is where I get lost. I think this means $\mathcal{NP}$-hard = $\mathcal{NP}$, and thus $X$ will reduce to its complement in this world.

$\endgroup$
  • 2
    $\begingroup$ That's a mathematical statement; it might require a mathematical explanation. $\endgroup$ – D.W. Jan 15 at 7:58
1
$\begingroup$

First note that $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard since $X$ is $\mathcal{NP}$-hard (try to see why). Since 3SAT is in $\mathcal{NP}$, any problem that can be reduced to 3SAT is in NP as well. So the statement suggests that the $\operatorname{co\mathcal{NP}}$-hard language $\overline X$ is in $\mathcal{NP}$.

On the other hand, saying that $\overline{X}$ is in $\mathcal{NP}$ is equivalent to saying that $X$ is in $\operatorname{co\mathcal{NP}}$. So in total we have $X \in \operatorname{co\mathcal{NP}}$ and $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard. So we get $X \leq_m^p \overline X$ by the definition of hardness.


Here is a bit of intuition of the fact that, if $X$ is $\mathcal{NP}$-hard, then $\overline{X}$ is $\operatorname{co\mathcal{NP}}$-hard.

Let $A$ be an arbitrary language in $\operatorname{co\mathcal{NP}}$. We have to show that $A \leq_m^p \overline{X}$. Let $B := \overline{A}$. Then $B$ is in $\mathcal{NP}$ and hence, $B \leq_m^p X$. This means there is a function $f$ computable in polynomial time, such that for an arbitrary word $x$, $x \in B$ if and only if $f(x) \in X$.

Now we show that $A \leq_m^p \overline{X}$. For a given word $x$. Using the same reduction $f$, we have $x \in A$ if and only if $x \notin B$ if and only if $f(x) \notin \overline{X}$ if and only if $f(x) \in X$.


Another note. Your intuition was right, but in the sentence

I think this means $\mathcal{NP}$-hard = $\mathcal{NP}$, and thus $X$ will reduce to its complement in this world.

You should have probably said $\mathcal{NP}$ = $\operatorname{co\mathcal{NP}}$.

$\endgroup$
  • 2
    $\begingroup$ By the way, you don't need explicit "edit tags" in your posts. It's only confusing to people coming to your post for the first time. Besides, if I want, I can always click to see the edit history of the post :-) $\endgroup$ – Juho Jan 15 at 12:04
  • $\begingroup$ I removed the tag. I thought it would have been more confusing to people who already read it if I edited/added paragraphs without hints $\endgroup$ – narek Bojikian Jan 15 at 12:07
  • 1
    $\begingroup$ I'm on my phone so it's hard to find a link, but I have a question about this on meta if you are interested. $\endgroup$ – Juho Jan 15 at 12:16
  • $\begingroup$ meta.stackexchange.com/questions/127639/… $\endgroup$ – narek Bojikian Jan 15 at 12:26
  • $\begingroup$ @narekBojikian You mention 'coNP-hard language --X is in NP. Then you mention that --X is in coNP-hard and use this to result in the final required reduction. Certainly it can't be the case that --X is in both NP and coNP-hard, so why do you get to pick and choose to use the fact that --X is in coNP-hard whilst ignoring your statement that --X is in NP? $\endgroup$ – SeesSound Jan 16 at 0:51

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.