私が知っていること（厳密には言えません）
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 クラスのいずれかに属していることを確認するために、問題にどのような種類の制約が必要ですか?