問題タブ [p-np]

たとえば、この多項式時間に関するすべてが私を混乱させます。セットから合計が 0 になる 4 つの整数のみを選択する多項式時間アルゴリズムでプログラムを作成したいと考えています。たとえば、次の整数のセット {8, 20, 3, -2, 3, 7, 16, -9} があるとします。4 以外のすべての可能な長さをチェックする必要なく、多項式時間のセットから合計が 0 になる 4 つの異なる整数のみを選択するにはどうすればよいですか? プログラムでは、4 以外の可能な長さを検索する必要がないことに注意してください。私の予想される解は {8, 3, -2, -9} = 0 です。セット { 8、20、3、-2、3、7、16、-9}。

編集:元のセットの長さだけを 8 から 100 の整数に増やしたとしても、{8, 3, -2, -9} の多項式時間解が見つかりますか? 0 ですが、100 個の整数のセットから、入力のサイズ (つまり、入力を格納するために使用されるビット数) に関して多項式の高速になりますか?

NP完全問題に還元可能であるが、その逆ではないNP問題の例は何ですか? NP と NP-complete について読んだとき、マッピングは 1 対 1 になるので、それらを分類するのはばかげていると思いました。しかし、確かに一方向にしか還元できないという問題があります。私はそれらを知りたいと思っています。

SharePoint プログラミングに取り組んでいます。私は最近、Sharepoin Pnp というトピックに精通しました。sharepoint pnp の性質は何ですか? いつ使用する必要がありますか？SharePoint pnp を使用したCSOMなどのWeb パーツやその他の SharePoint プログラミング パーツとの接続は何ですか? 親愛なる友人のアドバイスに感謝します。

私が知っていること（厳密には言えません）

PクラスとNPクラスの同等性について未解決の問題があることを私は知っています.P時間でNP問題を解決する既知のアルゴリズムがない限り、そのような問題の時空間解決可能性について区別します.

また、問題間で (多項式時間の) 削減を行うことができることも知っています。そのため、ある問題が特定のクラスに属することがわかっている場合、他の問題もこのクラスに属します。

また、シンプレックスアルゴリズムが線形計画法の問題を解決することも知っています。

知りたいこと

問題が NP クラスに属しているかどうかを「推測」する方法を知りたいです。問題の制約、制約の数、制約の「タイプ」と関係がありますか?

例

このリンクhttps://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/で、「購入による最大利益と動的計画法を使用して、最大で k 回株を販売します。

ただし、制約を増やすとどうなるでしょうか。純資産に制限があるとしましょう (無制限のお金はありません)、または一度に複数の株式を売買できますが、特定の時間内に売買できる株式の量に制限されているとします。 、または選択できるさまざまな会社の複数の在庫がありますが、所有できる在庫の総数には制限があります。

どのような種類の制約が問題を P から NP Class に「移動」するのをますます困難にするかをどのように知ることができますか? この問題が確実に P クラスまたは NP クラスのいずれかに属していることを確認するために、問題にどのような種類の制約が必要ですか?