Каждый ли распознаваемый по Тьюрингу неразрешимый язык имеет NP-полное подмножество?
Этот вопрос можно рассматривать как более сильную версию того факта, что каждый бесконечный распознаваемый по Тьюрингу язык имеет бесконечное разрешимое подмножество.
cc.complexity-theory
np-hardness
complexity-classes
np
decidability
veryltdbeard
источник
источник