Возможно ли сокращение от P до NP?

Question

Если X является поли-временем, приводимым к Y, мы ничего не можем сказать о X, даже если Y является NP-жестким, поэтому должны существовать некоторые разрешимые проблемы polytime, которые могут быть сведены к некоторым NP-трудным задачам. Может ли кто-нибудь привести некоторые примеры этого?

Answer 1

Пустой язык является единственным языком, который много-один сводится к пустопорожней,
и полный язык является единственным языком, который много-один сводится к полноценному языку.

Для всех других языков языков Y есть элемент Y и существует элемент дополнения Y.


Для всех полиномиальных по решаемые задачи X, для всех непустых без полных языков Y,
для всех элементов у из Y, для всех элементов г комплемента Y, в

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

является поли-временное сокращение от X до Y.