np-hard -closure

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 за полиномиальное время, потому что ясно:

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