NP-полнота

[cyb12]

Пусть задан язык $L$ в некотором алфавите, и известно, что задача распознавания принадлежности слова к этому языку является NP-полной. Что можно сказать об NP-полноте задаче распознавания "непринадлежности" слов к $L$? Вроде бы простой вопрос, но сразу появляются сомнения...

[Xaositect]

Можно сказать, что если она NP-полная, то NP=coNP.