これはNPの問題ですか？

Question

まず、私は理論などについてあまり知らないと言います。しかし、これが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の問題ですか？それとも私はこれを理解することができませんか？

Answer 1

このプログラムは、リストをどのように処理しますか？

確かに、定義を逆に実行するだけです。例えば

1. 電球を作成するには、1つのエネルギー + 1ガラスが必要です
2. エネルギーを作成するには、1つの火 + 1つの空気が必要です

等々。これは事実上シンプルなツリーウォークです。

OTOH、エネルギー +ガラスが電球を意味することをコンピューターに理解したい場合（「溶融ガラスの塊」ではなく）、問題を解決する機会がありません。おそらく、2人のゲーマーにEnergy + Glass = lightbulbに同意することはできませんでした！

Answer 2

問題をグラフとして簡単にモデル化し、完全な検索アルゴリズムを使用してソリューションを探すことができます。あなたが経験がないなら、それは調べるのにも役立つかもしれません 自動計画. 。複雑さと検索アルゴリズムに関する紹介も紹介しているため、私はそのテキストにリンクしています。