Блог

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

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

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

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

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

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