NP完全

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

NP完全問題についての

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

解決

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

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

締切

NP完全問題について。。

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

締切

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

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

解決

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

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

解決

NP完全問題について

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

解決

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

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

解決

NP完全 素因数分解をSATに変換するから派生 2進数の大小関係について

…以前「NP完全 素因数分解をSATに変換する」という質問をしたものです。 素因数分解をCNFに変換するスクリプトが出来たのですが、 a*b=cという関係だけだとa<=bのときもa>bの時も解になっ...…

解決

np完全問題とは何ですか

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

締切

NP困難について

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

締切

クラスNP

…クラスNP, クラスP, NP完全はそれぞれどのような違いがあるのでしょうか???…

締切

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

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

解決

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

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

締切

計算量(PやNP)について

…ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。 例えば、木の形で表せれる問題で、一つのノードに対する子がN個(定数) あり、深さX(未知、変数)に答え...…

解決

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

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

解決

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

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

解決

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

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

解決

PSPACE困難とNP困難について

…全てのNP困難な言語がPSPACE困難でもあるならばPSPACE=NPとなることの証明を教えてください。 NP⊆PSPACEが成り立ち、NP困難とPSPACE困難が等しい時にPSPACE=NPとなるのはなんとなくわかるのですが...…

締切

co-NPについて

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

解決

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

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

締切

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

Q質問する(無料)

おすすめ情報

Q&A検索履歴