問題タブ [np]

NP 困難な問題について混乱しています。
NP 困難な問題には、NP 完全と呼ばれる NP に含まれるものと、NP に含まれないものがあります。
例 : 停止問題は NP 困難であり、NP 完全ではありません。
しかし、なぜNP完全ではないのでしょうか?
問題が「NP困難だがNP完全ではない問題」と見なされるには、どのようなプロパティが必要ですか?

サイズ n の入力配列から k に加算されるすべてのペアを出力するプログラムを作成することは可能ですか? もしそうなら、どのように？この問題は NP-Complete だと聞きました。C/C++ のような典型的なプログラミング言語でこの問題の解決策を提供できるかどうか疑問に思っていました

私はコンピューター サイエンスの学生で、NP 問題の検証者ベースの定義を理解するのに問題があります。

定義は、「証明書」が与えられた場合、決定論的チューリングマシンによって多項式時間で検証できる場合、問題は NP にあると述べています。

しかし、証明書がまさに問題の解決策である場合はどうなるでしょうか? それはほんの少しであり、入力サイズによって明らかに多項式に制限されており、明らかに定数で検証可能であるため、多項式時間です。

したがって、各決定問題は NP に属します。

どこが間違っていますか？

これは私の最初のスタックオーバーフローの質問なので、優しくしてください。これがすでに殴打されている場合は、事前に謝罪します... NP でいくつかのスレッドを読みましたが、質問に対する興味をそそる答えが見つかりませんでした (どちらかといえば、いくつかの新しいものを思いつきました)。簡単に言うと:

1. 決定可能だが NP ではない決定問題はありますか?
2. もしそうなら、解決を求める問題は同等の決定問題より難しいですか?

私の疑惑は、最初の質問に対する答えは圧倒的に「はい」であり、2番目の質問に対する答えは圧倒的に「いいえ」であるということです.

最初のケースでは、問題の例として、「集合 S、S の部分集合 T、およびドメイン 2^S の関数 f が与えられた場合、T が f を最大化するかどうかを判断する」というものがあります。一般的な S、T、および f の場合、S のすべてのサブセット X について f(X) をチェックしないと、これを検証することさえできませんよね?

2 番目のケースでは...まあ、これは勘に過ぎないと認めます。何らかの理由で、答えに 1 ビット (決定問題の場合) が含まれているか、任意の (有限の) ビット数が含まれているかは問題ではないように思われます。 「回答」の一部としてTMが停止した後、テープに残された記号。

編集：実際、質問があります...関数の問題が決定の問題よりも「難しくない」ことをあなたの構造はどの程度正確に示していますか? どちらかといえば、決定問題よりも関数の問題に答える方が簡単ではないことを示しました...これは些細なことです。ずさんなやり方で質問した私のせいかもしれません。

NP に TM T1 があり、変数 X と (議論のために) 固定 P について「X は問題 P の解決策か」という問題を解決する場合、T1 が停止するすべての場所で停止する TM T2 が NP に存在することが保証されますか? 、どこでも「停止受け入れ」状態で終了し、テープに X のバイナリ表現などを残しますか?

非決定論的な多項式時間問題とNP完全問題とは何かを理解するのに苦労しています。私は多項式時間で解ける問題が何であるかを理解しており、ウィキペディアでNP問題について見ました。これについて読んだ後、私はいくつかの問題の例について考えようとしました。私が理解しているように、無向での深さ優先探索はNP完全です。これは、グラフが大きい場合（つまり、間違った決定をした場合は、代わりに他の選択を試みることができる）、各決定を非決定的に行うことができるためです（グラフサイズが小さい場合は多項式。）

数学をあまり使わずに、これらすべてのNP用語を簡単な例で簡単に説明できる人はいますか？

NP、NP-hard、および NP-complete の定義に関するこの質問への回答で、Jason は次のように主張しています。

停止問題は古典的な NP 困難問題です。これは、プログラム P と入力 I が与えられた場合、停止するかという問題です。これは決定問題ですが、NP にはありません。あらゆる NP 完全問題がこの問題に還元できることは明らかです。

停止問題は直感的に NP のどの問題よりもはるかに「難しい」問題であることに同意しますが、停止問題が NP 困難であるという正式な数学的証明を正直に思いつくことはできません。特に、NP のすべての問題 (または少なくとも既知の NP 完全問題) のインスタンスから停止問題への多項式時間多対 1 マッピングを見つけることができないようです。

停止問題が NP 困難であるという簡単な証明はありますか?

NP完全の定義は

次の場合、問題は NP 完全です。

1. それはクラス NP に属します
2. NP の他のすべての問題は多項式に変換されます。

では、NP の他のすべての問題が NP 完全問題に変換される場合、それはすべての NP 問題も NP 完全であることを意味するのではないでしょうか? 2つが同じである場合、2つを分類するポイントは何ですか?

つまり、NP 問題がある場合、(2) を通じて、この問題は NP 完全問題に変換できます。したがって、NP 問題は NP 完全であり、NP = NP 完全です。どちらのクラスも同等です。

これを自分で明確にしようとしているだけです。

私は、いくつかの人気のあるpythonパッケージをベースとして使用して、グラフとネットワーク用のオープンソース近似アルゴリズムライブラリに取り組んでいます。主な目標は、グラフとネットワーク上のNP完全問題の最新の近似アルゴリズムを網羅することです。この理由は、1）これをカバーする優れた（最新の）統合パッケージを見たことがないこと、および2）NP困難最適化問題の近似アルゴリズムについて学習するための優れた教育ツールになることです。

このライブラリを構築する際に、私はユニットテストを使用して健全性チェックを行っています（適切な開発者が行うように）。ユニットテストは、その性質上、近似アルゴリズムが正しい解を返さない可能性があるため、多少注意が必要です。現在、私はいくつかの小さなインスタンスを手作業で解決し、返された結果がそれに一致することを確認していますが、これは望ましくなく、実装の意味でスケーラブルでもありません。

近似アルゴリズムをユニットテストするための最良の方法は何でしょうか？ランダムなインスタンスを生成し、返される結果がアルゴリズムによって保証された範囲よりも小さいことを確認しますか？これには誤検知があるように思われます（テストはその時点で幸運であり、すべてのインスタンスが制限を下回ることが保証されているわけではありません）。

次の NP 完全問題があります。

与えられた:

• N × N フィールド内の位置のセット、
• m 個のノードのセット、および
• ノードの接続性グラフ (つまり、エッジが互いに接触しているノードのすべてのペアを表す無向グラフ)、および
• 接触範囲 R (N × N フィールドと同じ長さ単位)、

接続グラフを考慮してフィールド内のノードの配置を見つける (つまり、接触しているペアが R よりも近く、接触していないペアが R よりも遠いようにノードを配置する)、またはそのような配置が存在しないことを示します。

この問題を還元できる有名な NP 完全問題はありますか?

(問題の最適化バージョン、つまり最適な配置を見つけることも考えられます)

無向グラフの各ノードを正の重みに関連付けます。頂点パッキング問題は、ノード間のエッジを持つ 2 つのノードが選択されないように、最大​​の重みの合計を持つノードのサブセットを見つけることです。

二部グラフの頂点パッキング問題を解決する最も効率的な方法は何ですか? ノード数が 2 倍の最大フロー問題として定式化できました。より効率的で、おそらく直接的なアプローチはありますか?