NP困難

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

NP困難について

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

締切

PSPACE困難とNP困難について

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

締切

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

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

締切

NP困難問題は必ず指数時間で解けますか?

…宿題で大変困っています。 もしよろしければ教えて下さい。 NP困難問題で指数時間で解けない問題は存在するのでしょうか? よろしくお願いします。…

解決

NP困難の近似最適化について。

…整数計画問題で、あるネットワーク中の配送量を最大化する問題です。 小規模ではGLPKというソフトを使って最適値を出すことができました。 しかし、大規模になるとやはり無理でしたの...…

解決

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

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

解決

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

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

解決

アルゴリズム論の参考書

…アルゴリズム論のよい文献をさがしています。 データベース論ではなくてNP困難や貪欲アルゴリズム、最適化論、ヒューリスティック、離散数学に焦点を当てた実用的かつ理論的な参考書を...…

解決

この文の意味は・・・?

…この文の意味が分からず困っております。。。 The problems just listed are but a few of the thousands of NP-hard problems that have been identified. リストされただけの問題は存在するが 識別されたほんの数千の N...…

解決

co-NPについて

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

解決

m個のジョブをn台のCPUに分担する

…情報処理技術者試験の勉強会の時の、並列処理の話題だったんですが、誰も明快な答が出せなくて、ここに質問する事にしました。 どなたか知恵を貸して頂ければ、幸いです。 <問題> ...…

締切

素数探索はNP?

…「a以上b以下の範囲に素数が存在するか」 という問題はNPに入りますか? 入るとしたらどのように充足可能性問題に帰着できますか? 素数判定はPに入るらしいですが難しい理論が必要らしい...…

解決

ご祝儀の問題

…「結婚式のご祝儀は奇数」という話題から思いつきました (数学カテゴリなので、この話の真偽は置いておいてください)。 また、[ ]でくくったのは添え字(数列に使う下付き文字)です。 結...…

解決

NP完全問題について。。

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

締切

グラフの最長パスの求め方

…グラフの最長パスを求めるアルゴリズムにはどのようなものがあるのでしょうか。 例えば、以下のようなグラフであれば、最長パスは6になります。 ・-・-・-・-・ | | ・-・ また、以下...…

解決

辺彩色のアルゴリズム

…グラフ理論についての質問です。 平面グラフを辺彩色するのに必要な色の最小の数を求めるアルゴリズムがあるとききました。 しかし、調べてみましたがどのようなものかわかりません。...…

締切

東大入試っぽい(?)問題を自作したのですが、解けません・・・どなたか、解けますでしょうか?

…お世話様です。 2chの数学板で、 「東大入試の問題制作者になったつもりで問題を出せ」みたいなスレッドがあって、 おもしろそーだなーと思って、作ってみたのですが、 自分で、解け...…

解決

5000年後 AIと人間の関係はどうなっているか?

…何年後にどうかという事は分かり難いですが 製造業や一次産業でもロボットが働き サービス業でもAIが進出して来るでしょう 極端に言えばAI・ロボットは人間より優れていると言っていい...…

解決

m個の数字をn個のグループに分けるとき、

…m個の数字をn個のグループに分けるとき、 各グループの和s(i) ,(1<=i<=n) が、指定した比 r(0):r(1): ・・・ :r(n-1):r(n) ( = s(0):s(1): ・・・ :s(n-1):s(n) ) に一番近くなるようなグループ分けを...…

解決

デジカメ用充電器

…よくディズニーランドでショーやパレードをデジカメで1日撮影すると必ず電池がなくなります。 なので充電器が乾電池などで充電できる充電器がほしいと思っているのですが私が持ってい...…

解決

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

Q質問する(無料)

おすすめ情報

Q&A検索履歴