2
最初に私は理論などについてはあまり知らないと言うつもりです。しかし、これがNPかNP完全な問題かどうか疑問に思っていました。具体的には、サブセットサム問題の特殊ケースのように聞こえる。これはNPの問題ですか？
とにかく、私は最近、この考えを促したAlchemyと呼ばれるこのゲームがあります。基本的に4つの基本要素から始め、それらを組み合わせて他の要素を作ります。
あなたは要素
fire=basic element water=basic element air=basic element earth=basic element sand=earth+earth glass=sand+fire energy=fire+air lightbulb=energy+glass
を作るためにそれでは、コンピュータが唯一の4つの基本要素を作成することができます言わせますが、それは複数のセットを作成することができればそう、例えば、これは短い「レシピ」であります要素。したがって、他の要素を組み合わせて要素を作成するプログラムを作成します。このプログラムはどのように電球を作成するリストを処理しますか？
明らかに火災+空気=エネルギー、土壌+土砂=砂+火=ガラス、エネルギー+ガラス=電球です。
しかし、リストを処理してブルートフォース型の方法を使わずにすべての要素を調べてそのレシピをチェックすることなく、リストを処理するプログラムを書く方法は考えられません。
これはNPの問題ですか？それとも、私はこれを理解することができませんか？
役立つかもしれませんが、これはPrologの仕事のようです。 –
これはPにあり、したがってNPにもあります。しかし、それはNP完全ではありません。 – lijie
あなたは非常に簡単に検証を書くことができるので、少なくともNPに入っています。 –