np-hard - np 硬闭包

Question

if l1 is in NP-HARD, 所以对于每个 L2!=empty 集, l1*l2 is in np-hard.

什么时候：

l1*l2={(w1,w2) , w1 in L1 and w2 in L2}

这是真的还是假的，为什么？

我不能批准它，但我也找不到反例。

Answer 1

L1 * L2 是 NP 难的。

证明：令 L 为 NP 中的一种语言，令 f 为 L 到 L1 的约简，令 w2 在 L2 中。定义 g(x) = (f(x), w2)。现在 g 是 L 到 L1*L2 的多项式时间多对一约简，因为很明显：

x in L <==> (f(x), w(2)) in L1*L2