во-первых, я собираюсь сказать, что я не очень много знаю о теории и тому подобном. Но мне было интересно, была ли это NP или NP-полная проблема. Это звучит как частный случай проблемы суммы подмножества.
Во всяком случае, есть игра, в которую я недавно играл под названием «Алхимия», которая натолкнула меня на эту мысль. В основном вы начинаете с 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 основных элемента, но он может создать несколько наборов элементов. Итак, вы пишете программу для создания любого элемента путем объединения других элементов. Как эта программа обработает список, чтобы создать лампочку?
Очевидно, что огонь+воздух=энергия, земля+земля=песок, песок+огонь=стекло, энергия+стекло=лампочка.
Но я не могу придумать никакого способа написать программу для обработки списка и выяснить это, не выполняя метод грубой силы и не просматривая каждый элемент и не проверяя его рецепт.
Это проблема НП? Или я просто не могу в этом разобраться?
