NP困難について

質問

初めまして。NP困難について質問です。
AがNP困難とは「NPに属するどの問題もAに多項式時間で還元可能」
と定義されています。

それでNP困難について質問ですが、NP困難のクラスの問題というのは
その問題がNPに含まれてるかどうかは問わず、ただ上記の定義の条件
のみで定められていると考えていいのでしょうか。つまり
「NPの問題と同程度以上に難しい問題をNP困難」
「NP困難はNPのクラスに含まれてるか、含まれてないかは問わない」
か、ということです。

また、定義「NPに含まれる問題のうちNP困難なものをNP完全」より
NP困難に「NPに含まれる」という条件を加えたものが
NP完全で、NP完全∈NP困難となると思います。
どこか間違ってれば指摘して下さるとありがたいです。

回答No.1

Tacosan

単なるミスだと思いますが, 「NP完全∈NP困難」じゃなくって「NP完全⊂NP困難」ですね.
それ以外は全部 OK. coNP完全な問題は NP困難だけど (P ≠ NP の仮定のもとで) NP には含まれません.

お礼

考えに自信がもてました。ありがとうございました。