np-complete - 这是NP问题吗？

Question

首先，我要说我对理论之类的了解不多。但我想知道这是 NP 问题还是 NP 完全问题。这听起来特别像是子集和问题的特例。

无论如何，我最近一直在玩这款名为 Alchemy 的游戏，它激发了我的想法。基本上你从 4 个基本元素开始，然后将它们组合成其他元素。

因此，例如，如果您愿意制作元素，这是一个简短的“食谱”

fire=basic elementwater=basic elementair=basic elementearth=basic elementsand=earth+earthglass=sand+fireenergy=fire+airlightbulb=energy+glass

假设一台计算机只能创建 4 个基本元素，但它可以创建多组元素。所以你写了一个程序来通过组合其他元素来制作任何元素。该程序将如何处理列表以创建灯泡？

显然是火+空气=能量，土+土=沙子，沙子+火=玻璃，能量+玻璃=灯泡。

但我想不出任何方法来编写一个程序来处理列表并在不执行蛮力类型方法并遍历每个元素并检查其配方的情况下解决这个问题。

这是NP问题吗？还是我只是无法弄清楚？

Answer 1

How would this program process the list the create a lightbulb?

当然，您只是向后运行定义；例如

1. 制作一个灯泡需要 1 个能量 + 1 个玻璃
2. 创造能量需要 1 火 + 1 风

等等。这实际上是一次简单的树木漫步。

OTOH，如果你想让计算机弄清楚能量 + 玻璃意味着灯泡(而不是“一团熔融玻璃”)，你就没有机会解决这个问题。您可能无法让 2 名玩家同意能量 + 玻璃 = 灯泡!