多項式時間 の検索結果 (195件 1〜 10 件を表示)

多項式時間変換

…初めまして。 多項式時間還元について質問させて下さい。 問題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...…

締切

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

Q質問する(無料)

おすすめ情報

Q&A検索履歴

カテゴリ