問題タブ [np]

コンセプトの明確化が必要でした。問題が NP 完全であることを証明するために、リダクションを使用します。

ここで、L<=L' があるとします。L から L' への削減がありますか、それとも逆の方法で行うことはできますか? つまり、L が L' を使用して解決できる場合、L' は NP 完全であることを示すことができますか??

私はこれに関してかなり混乱しています。

例えば。ハム サイクルからハム パスへの削減については、逆方向にします。

また、「少なくとも k 個のエッジを持つグラフに s から t へのパスがあるかどうか」を示す必要があるという問題を、ハム サイクルからのリダクションで解決できません。

上記の問題について説明し、私を導いてください。ありがとう

一般的に、NPC に問題があると仮定します。それに制約を追加する（より困難にする）と、問題がNPHになる可能性はありますか？NPC と NPH の違いはわかっていますが、既存の NPC 問題に新しい制約を追加すると NPH になるか、NPC のままになるかを示す方法がわかりません。

私は何かがNPであることを証明する方法を学んでいます。Thomas Cormenのアルゴリズムの本の紹介で、彼は、ある問題の解決策が与えられれば、何かがNPであると述べています。これは、多項式時間で正しいことを確認できます。

問題が2x+9 = 55であり、正しいx値を見つけるのにどれくらいの時間がかかるかわからないふりをしましょう。しかし、問題を解くアルゴリズムが解23を返しました。それからそれがNPであることを示すために、 23を方程式に戻すだけで、それが多項式の時間を要して55を与えたかどうかを確認できますか？ありがとう。

問題がNP困難であるというスケジューリング問題をいくつか見ました。私の質問は、1）問題がNP困難であると言うとき、それはNPにないことを意味しますか？それがNPである場合、問題はNP完全であると言うからです。a）NPにある場合b）NP困難である場合、問題はNPCにあることを私は知っています。

NPC 問題のセットの構築を開始するには、最初の問題があったはずです。そうして初めて、NP の問題が NPC の最初の問題に還元可能であることを示すことによって、集合 NP から集合 NPC に問題を追加することができます。では、NPC に最初に追加された問題は何であり、それが実際に NPC であると誰かがどのように結論付けたのでしょうか。

(注: Google で検索しましたが、答えはありません。ここの誰かの教授がクラスでこのようなことを言っていたことを願っています)

NP と NP 完全問題の違いを調べていました。私はジェイソンによるStackOverflowでこの素晴らしい答えに出くわしました。NP完全問題について、彼は言った

多項式時間で他の NP 問題 Y を X に簡約できる NP 問題 X。これは直観的に、X を素早く解く方法を知っていれば、Y を素早く解くことができることを意味します。正確には、X のインスタンス x を多項式時間で Y のインスタンス y = f(x) に変換する多項式時間アルゴリズム f が存在する場合、Y は X に還元可能です。 f(x) へはイエスです。

私の質問は、NP 完全問題は X と Y のどちらですか?

2 つの配列があり、それぞれが 2 つの整数 (int1,int2) のペアで構成されています。各配列のペアの最初の値に対してのみ合計を計算し、2 番目の値に (たとえば) 乗算を適用したいと考えています。明らかに、このコードを書くと:

tab3 の結果は tab3=array([[1, 9],[2, 9],[0, 8]]) になります

金額は第 2 部でも適用されました。しかし、私は (1+0),(1+1),(0+0) を取得したいので: tab3=array([1,2,0])

配列でループを実行せずにこの結果を得ることは可能ですか?

問題が NP 完全であるためには、それがクラス NP に属している必要があり、それを NP 完全問題に還元するための多項式時間アルゴリズムが存在する必要があります。

ここで、reduction に指数時間アルゴリズムしかない場合はどうなるでしょうか。この問題はまだ NP-complete と呼ばれますか? それとも、そのような既存の問題はありませんか？

EDIT：また、そのような問題があるかどうか教えてください。もしあれば、それはどのクラスに属しますか？

NP クラスに該当する問題の場合:

1. 問題の解には、多項式出力の長さがなければならず、
2. 解は多項式時間で検証可能でなければなりません。

多項式出力の長さの意味は何ですか?

PS：多項式出力の長さは、出力が多項式時間で検証可能であるために必要な前提条件だと思います。(しかし、解は多項式時間で検証できると言うだけで十分です。)