Is A times B of NP-complete languages A and B necessarily NP-hard?

Question

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?

Answer 1

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.