NP完全問題

の検索結果 (260件 1〜 20 件を表示)

NP完全問題についての

NP完全問題についての質問です (1) NP完全問題とは多項オーダーの計算量で解決可能な問題のクラスですか、 問題のサイズをnとしたとき「nの階乗」,「2のn乗」 オーダーとなる問題は NP完全...…

解決

NP完全問題について。。

…今、NP完全問題とSATについて勉強しています。 Wikiとかでも調べていて、一応自分なりに解釈をすすめて いるところですが、言い回しが難しくて理解しきれません。 簡単に、NP完全問題とSAT...…

締切

素因数分解は,NP完全問題でしょうか?

…タイトル通りです. 素因数分解はNP完全問題でしょうか? それとも,クラスNPに属するだけでしょうか? ド素人ですのでできるだけ解り易くお願いいたします・・ ・.…

解決

NPクラス、Pクラス、NP完全問題について教えてください

…こんにちは。 授業でNPやPというような言葉が出てくるのですがいまいち理解できません。 あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判...…

解決

NP完全問題、NP困難問題についての質問です。

…下記の問題が存在するとされているか、存在しないとされているか、もしくはどちらでもないかを教えてください。 どちらでもないものに対しては、簡単でいいのでなぜどちらでもないと...…

締切

NP完全問題について

NP完全問題について、最新の研究状況をお教えください。(当方、理系の大学出で、少し概念は学びました)また、今関連のHPやメーリングリストがありましたらお教えください。…

解決

np完全問題とは何ですか

…例とか、特にどんなところが難しいかを教えてください。 友達の話ではチンプンカンプンで、何の為にそれを使って議論してるか分かりません。…

締切

部分和問題がわかりません。

…部分和問題がわかりません。 [問題] n個の整数が配列Aに格納されていて、整数xの値を与えたときに、 A[i] + A[j] = x となるi,jが存在するかどうかを判定する、なるべく効率のよいアルゴリズム...…

解決

NP完全 素因数分解をSATへ変換する

…素因数分解をSAT(充足可能性問題)に変換したいと思っています。 掛け算をCNFに変換しようと思ったのですが、やり方がよくわかりません。 そもそも素直に掛け算をCNFに変換するとXORが必要...…

解決

高速な和積形命題論理式の含意関係判定法

…2つの和積形命題論理式が与えられています。 この2つの式に含意関係が成り立つか判定したいのです。 この問題はco-NP完全問題でまともにやるととても時間がかかります。 そこで次のよう...…

解決

計算理論についての質問です

…NP完全の問題に関して指数時間アルゴリズムがあるからといってP≠NPとはいえないのはなぜでしょうか?…

解決

P≠NP問題についての質問です。

…P≠NP問題についての質問です。 この問題の議論されている意味が分かったような? 分からんような?、なので質問します。 大方の研究者は、「P≠NP」ではないか?、という予想をしているよ...…

解決

クリーク問題の計算複雑度

…最近計算量理論を独習する中で「クリーク問題」なるものを知りました。 <クリーク問題> 入力: グラフG、正整数k 質問: Gは大きさkのクリーク(完全グラフ)を含むか? このクリーク問題...…

締切

「P≠NP予想」について、数学が苦手な中学生でも分かるように説明してほしいです。

…Wikipediaを見てもサッパリ訳が分からなくて(当然でしょうか^^;)、 比較的くだけた表現のニコニコ大百科(http://dic.nicovideo.jp/a/p%E2%89%A0np%E4%BA%88%E6%83%B3)を見ても、2割3割くらいしか理解できません...…

締切

最短経路探索について

…下記のような問題をプログラムで解決する時、この問題を最短経路問題の「〇〇問題」に当てはめられるとしたらどれになるのでしょうか? プログラムが作りたいのですが、どのようにすれ...…

締切

ハミルトン閉路とNP

…ハミルトン閉路問題はNPに属する、という事を証明したいのですが… これって HCがPに属することを証明すれば良いのでしょうか? ちょっと迷走しちゃってます……

締切

特定比率の直方体の中に複数の直方体を自動的に隙間なく入れる方法

…たとえば段ボール箱(直方体)があるとします。 段ボール箱の縦横高の長さは特定の比率の縦横比ですが、大きさは決まっていません。 その段ボール箱の中に、できるだけ隙間なく、購入し...…

締切

NPC概念の意義の問題点について

…とにかく、何か分かっていることがあれば教えてください。…

解決

最新の暗号化技術についての解説を御願いします。

…量子暗号技術にも公開鍵方式が応用的に使われているのでしょうか?…

解決

ハミルトングラフ

…ハミルトングラフになるときって、頂点がn個で、任意の二つの点v,w隣接してないとき deg(v)+deg(w) ≧n なんで、 つまり頂点vとwの次数の合計がn以上なら、成り立つんですよね? でも閉路グラ...…

解決

検索で見つからないときは質問してみよう!

Q質問する(無料)

おすすめ情報

Q&A検索履歴