np-hard - np-hard -閉鎖

Question

if l1 is in NP-HARD、したがって、すべての L2!=空のセットに対して、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 に多対 1 に縮小した多項式時間です。

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