Каждый ли распознаваемый по Тьюрингу неразрешимый язык имеет NP-полное подмножество?

9

Каждый ли распознаваемый по Тьюрингу неразрешимый язык имеет NP-полное подмножество?

Этот вопрос можно рассматривать как более сильную версию того факта, что каждый бесконечный распознаваемый по Тьюрингу язык имеет бесконечное разрешимое подмножество.

veryltdbeard
источник

Ответы:

21

Нет.

Неразрешимые неразрешимые по Тьюрингу языки могут быть унарными (определитьxL если x=00000Таким образом, единственные сложные строки состоят исключительно из 0). Теорема Махани говорит, что ни один унарный язык не может быть NP-полным, если P = NP.

Питер Шор
источник
Спасибо за ответ и полезный указатель на теорему Махани!
Veryltdbeard