多項式時間

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

多項式時間変換

…初めまして。 多項式時間還元について質問させて下さい。 問題Aが問題Bに多項式時間還元できるかの証明として (1)問題Aの任意の問題例xを多項式時間で問題Bの問題例に変換しているか. yes:...…

解決

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

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

解決

巡回セールスマン問題: NPについて

…NP問題である巡回セールスマン問題について質問です. NP問題には,「非決定性チューリングマシンによって多項式時間で解くことができる決定問題」「証拠が与えられれば,その答えがYesであ...…

解決

ド・モルガンの時間計算量について

…和積標準形(CNF)から積和標準形(DNF)に変換する際に、ド・モルガンの法則を適用すれば可能ですが、このときの時間計算量を教えてください。 多項式時間でしょうか? それとも指数時間かかる...…

締切

この問題はNP?(円周率πの10進展開中に3がx個連続して現れるか?)

…以下のような判定問題があります。 <円周率中の3の連続出現> 入力: 正整数x 質問: 円周率を10進で展開した無限数列(3.14159...)に数字3がx個連続して並ぶ箇所があるか? この問題はクラスN...…

締切

脳と量子コンピュータ

…NP問題を多項式時間で「直感的に」 解けてしまう人がいたとします。 その場合、人間の脳は、量子コンピュータだと言えるでしょうか? また、そういう実例というのは存在するでしょうか? ...…

解決

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

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

解決

NP困難について

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

締切

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

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

解決

P≠NP問題

…P≠NPの時クラスPはクラスNPには属さない P=NPならばそれはP=Pになってしまうからだ。 Nが仮に0とすればNPもは0になるがこれではP/0=Pというように解なしという答えになってしまう。 次に、P...…

締切

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

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

解決

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

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

解決

【P≠NP予想】容疑者Xの献身を観たのですが

…容疑者Xの献身を観たのですが、 映画の一場面で「P≠NP問題」の話題が出てきました。 その中で、 「数学の問題について、自分で考えて答えを出すのと、他人から答えを聞いて、その答え...…

解決

素因数分解について

…ものすごく大きな素数二つを掛け合わせた数を素因数分解することは難しい、というようなことを本で読みました。 これって暗号を作ることにも利用されているみたいですが、どうしてこ...…

締切

未解決問題 P=NP について

…資料が英語なので、意味すら理解していません。 なぜ、P=NPが未解決問題になったのでしょうか? P=NPが成立しないと思います。 数字を当てはめても、せいぜい P=-0 N=+0 しか思いつきません...…

解決

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

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

解決

NP完全問題について。。

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

締切

対偶による証明法と背理法による証明について

…数学Iの内容なのですが自分の使っている参考書に 対偶による証明法も一種の背理法と考えることが出来る。 命題p⇒qが真であることをいうために¬qと仮定して¬pが導かれたとする。 pでは...…

締切

アルゴリズム 教えてください

…必修科目「数学」、選択必修科目「歴史」と選択必修科目「地理」の3科目がある。 ある2人の学生に対して「二人とも進級」か「一人が留年」あるいは「二人とも留年」を出力する問題を考...…

締切

ハミルトン閉路とNP

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

締切

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

Q質問する(無料)

おすすめ情報

Q&A検索履歴