# An NP-hard problem reduces to its complement?

I found this statement in a true/false test section: 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.

• That's a mathematical statement; it might require a mathematical explanation. – D.W. Jan 15 '20 at 7:58

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

• 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 :-) – Juho Jan 15 '20 at 12:04
• 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 – narek Bojikian Jan 15 '20 at 12:07
• 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. – Juho Jan 15 '20 at 12:16
• meta.stackexchange.com/questions/127639/… – narek Bojikian Jan 15 '20 at 12:26
• @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? – SeesSound Jan 16 '20 at 0:51