PからNPに還元は可能ですか？

Question

Xが多項式時間でYに還元できる場合、YがNPハードであってもXについては何も言えないので、いくつかのNP困難な問題に還元できるポリ時問題が存在しなければならない。 誰かに例を挙げてもらえますか？

Answer 1

空の言語は、空の言語に還元多一つのみ言語、
であり、完全な言語は、完全言語に還元多一つである唯一の言語です。

その他言語Yの場合、Yの要素があり、Yの補数の要素があります。全てpolytime解ける問題Xについて


、すべての非空非フル言語Y、
ためのYのyのすべての要素のために、Yの補数のすべての要素Zの、

solve the input 
if the answer is yes: 
    output y 
else: 
    output z 

でありますXからYへの多時間短縮。