NP困難 の検索結果 (214件 1〜 10 件を表示)

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に属する問題はどの程度複雑といえるのでしょうか? お願いします。…

解決

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

Q質問する(無料)

おすすめ情報

Q&A検索履歴

カテゴリ