- ベストアンサー
co-NPについて
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
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完全なのはほとんど自明ですし.
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
「coNP に属する」という情報だけでは「さぁ」としか答えられません. P ⊂ coNP だから, 「P に属する」問題は全て「coNP に属する」と言えてしまいます. ちなみに coNP完全なら NP困難.
お礼
この問題にも答えていただき大変ありがとうございます。まず確認させていただきたいのですが、coNP完全の定義は「言語LがcoNPに属していて、かつcoNPに属すすべての言語L'が言語Lに多項式時間帰着可能」でよろしいのですか？ 「coNPに属す」だけでは、なにもわからないのですか。。。。私が行ったのは、ある問題がNP困難ということは証明できたので、その問題のクラスを考えたときにcoNPでした。
関連するQ&A
- NP困難について
初めまして。NP困難について質問です。 AがNP困難とは「NPに属するどの問題もAに多項式時間で還元可能」 と定義されています。 それでNP困難について質問ですが、NP困難のクラスの問題というのは その問題がNPに含まれてるかどうかは問わず、ただ上記の定義の条件 のみで定められていると考えていいのでしょうか。つまり 「NPの問題と同程度以上に難しい問題をNP困難」 「NP困難はNPのクラスに含まれてるか、含まれてないかは問わない」 か、ということです。 また、定義「NPに含まれる問題のうちNP困難なものをNP完全」より NP困難に「NPに含まれる」という条件を加えたものが NP完全で、NP完全∈NP困難となると思います。 どこか間違ってれば指摘して下さるとありがたいです。
- 締切済み
- 数学・算数
- 計算量(PやNP)について
ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。 例えば、木の形で表せれる問題で、一つのノードに対する子がN個(定数)あり、深さX(未知、変数)に答えがある場合、計算量は N^X(NのX乗) になると思います。 N^Xは計算量のクラス(NP困難やNP完全等)でいうと何に属するのでしょうか？
- ベストアンサー
- 数学・算数
- NP完全問題についての
NP完全問題についての質問です （1）NP完全問題とは多項オーダーの計算量で解決可能な問題のクラスですか、 問題のサイズをｎとしたとき「ｎの階乗」，「２のｎ乗」オーダーとなる問題は NP完全問題のうちには入らない？ （2）PSPACE完全問題とは何か（NP完全問題はPSPACE問題に含まれる（？）） 以上です．よろしくお願いします．
- ベストアンサー
- 数学・算数
- NPクラス、Pクラス、NP完全問題について教えてください
こんにちは。 授業でNPやPというような言葉が出てくるのですがいまいち理解できません。 あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判定問題などです。似たような言葉がいろいろ出てきてよく分からないです。これらの用語のうちで意味が同じようなものもあるのでしょうか？ 自分なりに理解したことを書くと Pクラスというのはその問題が現実的な時間内で解けて、NPクラスとは時間がかかりすぎて解けないというふうに理解しています。 NPクラスには最長パスを求めるアルゴリズムや大きな素数同士の積の因数分解などだと思います。ウィキペディアでも調べたのですが言葉が難しくて曖昧にしか分かりませんでした。 また、判定問題やハミルトン問題などについても知りたいです。何か良いサイトがありましたら紹介してもらえるとありがたいです。 ご回答よろしくお願いします。
- ベストアンサー
- 数学・算数
- NP完全問題について。。
今、NP完全問題とSATについて勉強しています。 Wikiとかでも調べていて、一応自分なりに解釈をすすめて いるところですが、言い回しが難しくて理解しきれません。 簡単に、NP完全問題とSATについてのご説明を どなたかしていただけないでしょうか？ また良いサイトがあったら教えてください。
- 締切済み
- 数学・算数
- 素因数分解は，NP完全問題でしょうか？
タイトル通りです． 素因数分解はNP完全問題でしょうか？ それとも，クラスNPに属するだけでしょうか？ ド素人ですのでできるだけ解り易くお願いいたします・・・．
- ベストアンサー
- 数学・算数
- 【P≠NP予想】容疑者Ｘの献身を観たのですが
容疑者Ｘの献身を観たのですが、 映画の一場面で「Ｐ≠ＮＰ問題」の話題が出てきました。 その中で、 「数学の問題について、自分で考えて答えを出すのと、他人から答えを聞いて、その答えが正しいかどうかを確認するのとではどちらが易しいか（難しいか）？ ただし、その問題には必ず答えが存在する。」 というセリフがありました。 恐らく、前者がクラスＰ、後者がクラスＮＰのことを表していると思われます。 しかし、「どちらが易しいか？（難しいか？）というのは、「Ｐ≠ＮＰ問題」の本質ではないような気がします。（Ｐの方がＮＰより解くのが大変ですよね・・） Ｐ≠ＮＰ問題の核心部分は、「Ｐ⊂ＮＰが成り立つかどうか？（ＮＰ⊂Ｐは自明）」ではないでしょうか？ 自分は映画を見ていて、「そんなの、他人から答えを聞いてその答えが正しいかどうかを確認する作業の方が、自分で答えを考え出すのより何百倍も簡単だろ！！」と思ってしまいました。 詳しい方解説お願いします！！！
- ベストアンサー
- 数学・算数
- クリーク問題の計算複雑度
最近計算量理論を独習する中で「クリーク問題」なるものを知りました。 <クリーク問題> 入力: グラフG、正整数k 質問: Gは大きさkのクリーク(完全グラフ)を含むか? このクリーク問題の計算複雑度はNP完全とのことです。一方 <3クリーク問題> 入力: グラフG 質問: Gは大きさ3のクリークを含むか? この3クリーク問題の計算複雑度はPとのことです。そして3に限らず(5とか100とか)任意の数の場合でやはり計算複雑度はPとのことです。(下記URL参照) ここで疑問に思ったのですが、(PとNPは同一ではないという前提で)上の二つ(クリーク問題はNP完全、3クリーク問題はP)は矛盾してはいないでしょうか。すなわち、3クリーク問題、4クリーク問題、...がPで解けるのであればクリーク問題もPで解けるのでは、ということです。 どなたかこの件を解説していただけないでしょうか。 どうぞよろしくお願いいたします。 http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/30126probs2.pdf http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/ex_2_ans.pdf
- 締切済み
- 数学・算数
- この問題はNP?(円周率πの10進展開中に3がx個連続して現れるか?)
以下のような判定問題があります。 <円周率中の3の連続出現> 入力: 正整数x 質問: 円周率を10進で展開した無限数列(3.14159...)に数字3がx個連続して並ぶ箇所があるか? この問題はクラスNPに属するのでしょうか? たとえば「証明」が与えられたとき、その正しさを入力サイズ(この場合はx?)の多項式時間で検証できればNPに属するわけですが、 この場合の「証明」とは円周率中の3がx個並んだ箇所を「ほら、i桁目からj(=i+x-1)桁目に3がx個並んでいるよ」と円周率を小数点以下j桁目まで書いて示すことなのか? ↓ そうだとしたら、その検証は円周率をj桁目まで適当な方法で計算することなのか? ↓ そうだとしたら、xの多項式時間で円周率をj桁目まで計算出来るか? ↓ 計算コストはxとは独立なのでは? などと考えるうちに分からなくなってしまいました。 どうぞよろしくお願いいたします。
- 締切済み
- 数学・算数
- 大学受験用の化学の参考書を探しています
私は理論化学が苦手で、特に計算が多い、複雑な問題は特に苦手です。なので、今理論化学について良い参考書・問題集を探しています。理論化学のみでも、全分野入っていてもどちらでもいいので、何かいい本がありましたら教えてください。
- ベストアンサー
- 化学
お礼
本当はNP困難とわかった問題をクラスNPに属すことをしたかったんですが、どうしても解の検証が非決定性機械で多項式時間判定できなかったのでcoNPにしたんですよ。意味はなかったみたいですね（笑） 今回は質問に答えていただき誠にありがとうございます。なかなかcoNPに関する記述が載っている物がなく困っていました。