最初に言っておきますが、私は理論などについてよく知りません。しかし、これが NP なのか NP 完全な問題なのか疑問に思っていました。具体的には、部分和問題の特殊なケースのように聞こえます。
とにかく、私が最近プレイしている Alchemy というゲームが、この考えを促しました。基本的には、4 つの基本要素から始めて、それらを組み合わせて他の要素を作成します。
たとえば、要素を作成する場合、これは短い「レシピ」です。
火=基本要素 水=基本元素 空気=基本的な要素 土=基本元素 砂＝土＋土 ガラス＝砂＋火 エネルギー＝火＋風 電球＝エネルギー＋ガラス
では、コンピュータが 4 つの基本的な要素しか作成できなかったとしますが、要素の複数のセットを作成できます。したがって、他の要素を組み合わせて任意の要素を作成するプログラムを作成します。このプログラムは、電球を作成するリストをどのように処理しますか?
明らかに、火+空気=エネルギー、土+土=砂、砂+火=ガラス、エネルギー+ガラス=電球です。
しかし、リストを処理するプログラムを作成し、ブルートフォース型のメソッドを実行してすべての要素を調べ、そのレシピを確認することなくそれを理解する方法は考えられません。
これはNPの問題ですか？それとも、これを理解できないだけですか？