co-NPについて

質問

計算の複雑性理論について勉強しているのですが、ある問題がクラスco-NPに属すことがわかったんのですが、そもそもco-NPに属する問題はどの程度複雑といえるのでしょうか？お願いします。

回答No.2

Tacosan · ベストアンサー

coNP完全の定義はそれで OK, だったような気がします. 普段 coNP は使わないので (苦笑).
ちなみに「L が NP完全 if and only if L の否定が coNP完全」というのもあったような気がします.
で, 「coNP に属するだけでは何とも言えない」というのは, つまるところ「NP に属するだけでは何とも言えない」というのと同じです. 「P ⊂ NP ∩ coNP」だから, P に属する問題は全て NP (や coNP) に属します. つまり, 「P に属する問題」を「NP (や coNP) に属する」と言っても, 数学的な問題はありません. あまり広いクラスを考えてもしょうがないので, P に属することがわかっている問題を「NP に属する」ということはしませんが.
まあ, 普通 NP困難なら「難しい」と言いますね. それ以上先にもっていく (coNP の証明など) ことはあまりしないんじゃないかなぁ? 特に「NP完全な問題の否定」だったりすると, coNP完全なのはほとんど自明ですし.

お礼

本当はNP困難とわかった問題をクラスNPに属すことをしたかったんですが、どうしても解の検証が非決定性機械で多項式時間判定できなかったのでcoNPにしたんですよ。意味はなかったみたいですね（笑）
今回は質問に答えていただき誠にありがとうございます。なかなかcoNPに関する記述が載っている物がなく困っていました。

回答No.1

Tacosan

「coNP に属する」という情報だけでは「さぁ」としか答えられません.
P ⊂ coNP だから, 「P に属する」問題は全て「coNP に属する」と言えてしまいます.
ちなみに coNP完全なら NP困難.

お礼

この問題にも答えていただき大変ありがとうございます。まず確認させていただきたいのですが、coNP完全の定義は「言語LがcoNPに属していて、かつcoNPに属すすべての言語L'が言語Lに多項式時間帰着可能」でよろしいのですか？
　「coNPに属す」だけでは、なにもわからないのですか。。。。私が行ったのは、ある問題がNP困難ということは証明できたので、その問題のクラスを考えたときにcoNPでした。