1
$\begingroup$

If both $A$ and $B$ are NP-complete languages, would $A \times B$ be necessarily NP-hard? Here, $A \times B = \{\langle u,v \rangle \mid u\in A, v\in B\}$.

So my colleague's answer was no, it's not necessarily NP-hard because you can verify in polynomial time that $u \in A$ and the same for $v \in B$, but you see this is not the case I said, and when I tried to explain why this is wrong, I mumbled and stumbled because I suddenly came to realize that I don't really comprehend the concept to its full depth!

Any way I said if $\langle u,v \rangle$ was not NP-hard to decide, then also would the language $A$ for instance, because you can look at $A\times A$ as a reduction from $A$.

My question is, if I'm right what's my colleague's error and how to explain it, and if I'm wrong which I guess I'm not (this far I do know), then what's wrong about my theory?

$\endgroup$
7
$\begingroup$

Yes, the problem remains NP-hard. Reducing to $A\times A$ doesn't exactly solve the problem, since you want to reduce to $A\times B$.

However, you can proceed as follows: since $B$ is NP-hard, then $B\neq \emptyset$. Thus, there exists $w\in B$. Fix such $w$. We now show that $A\le_p A\times B$: given input $u$, the reduction outputs $\langle u,w \rangle$.

Clearly this can be done in polynomial time, since $w$ is fixed.

Now, since $w\in B$, then $u\in A\iff \langle u,w \rangle\in A\times B$, and we're done.

As for your question "where is my colleague wrong": you can indeed verify in polynomial time whether $\langle u,v \rangle\in A\times B$ if you are given witnesses for the membership of $u\in A$ and for $v\in B$. This shows that $A\times B\in NP$, but it has nothing to do with hardness.

Intuitively, membership in NP is an upper bound on the complexity, whereas NP-hardness is a lower bound.

$\endgroup$
  • $\begingroup$ You can't reduce to AxA but you can to Axu, this sounds strange, but other than that I think I got your point, anyway my question remains, how to explain what's wrong about my colleague's theory? $\endgroup$ – Anwar Saiah Mar 25 '18 at 20:19
  • $\begingroup$ @AnwarSaiah - I've added an explanation to the answer. $\endgroup$ – Shaull Mar 25 '18 at 20:31

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.