問題タブ [np]

NP、NP-Complete、NP-Hardの違いは何ですか?

私はウェブ全体に多くのリソースがあることを知っています。あなたの説明を読みたいのですが、その理由は、それらがそこにあるものとは異なるか、または私が認識していない何かがあるからです.

学校の時間割を作成するアルゴリズムの既知の解決策があるかどうか疑問に思っていました。基本的には、特定のクラス-科目-教師の関連付けについて、(教師とクラスの両方のケースで)「時間分散」を最適化することです。入力時に互いに関連付けられたクラス、授業科目、および教師のセットがあり、そのタイムテーブルは午前 8 時から午後 4 時の間に収まると仮定できます。

そのための正確なアルゴリズムはおそらくないと思いますが、誰かがそれを開発するための適切な近似またはヒントを知っているかもしれません。

P = NPは今のところ解決されていないことは知っていますが、次のことについて誰かに教えてもらえますか。この問題に取り組むのに役立つ可能性のある、現在最も有望な数学的/コンピューター科学的方法は何ですか。それとも、これまでに役立つ可能性があることが知られているそのような方法はありませんか？この分野で行われた研究のすべて/ほとんどを見つけることができるこのトピックに関する（無料の）概要はありますか？

それぞれが値を持つアイテムのセットを指定して、コレクションに含める各アイテムの数を決定し、合計値が指定された制限以下になり、合計値ができるだけ大きくなるようにします。

例：

組み合わせを決定するアルゴリズム (ナップザックやビン パッキングなど) を探しています。どんな助けでも感謝します。

計算理論をブラッシュアップしようとしていますが、これに対する解決策がわかりません：

NP問題の発見とα因数分解の問題の縮小の発見に関係しているのではないかと感じています。

次のうち、問題 X の最も正確な分類はどれですか?

• XはNPにある
• X は P にある
• X は O(n ² )にあります
• X は Θ(n ² ) にあります。

誰かが私にこれの答えを説明していただければ幸いです。

NPかPのどちらかだと思いますが、よくわかりません

巡回セールスマン問題、MAX-SAT、グラフの最小色数の検出など、NP困難であることが知られている多くの最適化問題があります。この種の問題を考えると、私は次の問題の複雑さに興味があります。

NP困難最適化問題と候補解Sが与えられた場合、Sは問題の最適解ですか？

直感的には、より良い解決策を推測してそれを証人として使用することで最適化問題への答えに反論するのは簡単なので、これは共同NP困難であるように思われますが、これをどのように示すかわかりません。実際、私はこの問題の複雑さについて推論する方法を本当に知りません。

この決定問題の複雑さに関する適切な下限を知っている人はいますか？これがco-NPハード、PSPACEハードなどであるかどうかを知ることは本当に興味深いでしょう。

最近、 NPとPに関する記事を読みました。与えられた単語の組み合わせを見つける問題は NP 問題ですか? たとえば、指定された単語antoの場合、結果は anot、toan などになります。私が知ったように、多項式時間で問題の解を確認できるときはいつでも、それは NP の下にあることを意味します。組み合わせの問題は NP に入るのですか？

これは、私が NP と P をよく理解しているかどうかを知るためのものです。

問題をNPとPに分割する主な意図または主な用途は何ですか? これには歴史的な理由がありますか、それとも私たちを助けるためにこれらの概念を作成したのでしょうか? もしそうなら、これらはどこで私たちを助けることができますか?

NP 困難な問題を効率的に解決するためのツールを実装する必要があり、メモリ使用量の爆発 (場合によっては出力サイズが入力サイズに対して指数関数的) が避けられない可能性があり、実行時のこのツールのパフォーマンスが特に心配であるとします。時間。基礎となる理論が理解できたら、ソース コードも読みやすく理解しやすいものでなければなりません。この要件は、ツール自体の効率と同じくらい重要です。

個人的には、これらの 3 つの要件を満たすには、c++、scala、java の 3 つの言語が適していると考えています。それらはすべて、異なる構造を比較したり、同じアルゴリズム (これも重要です) を異なるデータ型に適用したりできるようにする、データ型の適切な抽象化を提供します。

C++ には、静的にコンパイルおよび最適化されるという利点があり、関数のインライン化 (データ構造とアルゴリズムが慎重に設計されている場合) およびその他の最適化手法を使用すると、かなり良好な可読性を維持しながら、純粋な C に近いパフォーマンスを実現できます。データ表現にも細心の注意を払うと、キャッシュ パフォーマンスを最適化できます。これにより、キャッシュ ミス率が低い場合に桁違いの速度が得られます。

Javaは代わりにJITコンパイルされているため、実行時に最適化を適用できます。このカテゴリのアルゴリズムでは、異なる実行間で異なる動作を持つ可能性があり、プラスになる可能性があります. 代わりに、そのようなアプローチがガベージコレクターに悩まされる可能性があることを恐れていますが、このアルゴリズムの場合、メモリを継続的に割り当てるのが一般的であり、Java ヒープのパフォーマンスは C/C++ よりも優れていることで有名です。言語内に独自のメモリマネージャーを実装すると、優れた効率を実現します。代わりに、このアプローチではメソッド呼び出しをインライン化することができず (パフォーマンスが大幅に低下します)、キャッシュ パフォーマンスを制御することもできません。長所の中には、C++ よりも優れた簡潔な構文があります。

scala に関する私の懸念は、多かれ少なかれ Java と同じであり、さらに、コンパイラーと標準ライブラリーに関する深い知識がなければ、言語がどのように最適化されるかを制御できないという事実です。しかしまあ、私は非常にきれいな構文を取得します:)

この件についてどう思いますか？あなたはすでにこれに対処しなければなりませんでしたか？これらの言語のいずれかで、そのようなプロパティと要件を持つアルゴリズムを実装しますか、それとも何か他のことを提案しますか? それらをどのように比較しますか？