Является ли это проблемой NP?

Question

Вначале я собираюсь сказать, что не знаю много о теории и т. Д. Но мне было интересно, была ли эта проблема 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 основных элементов, но это может создать несколько наборов элементы. Таким образом, вы пишете программу для создания любого элемента путем объединения других элементов. Как эта программа будет обрабатывать список, создавая лампочку?

Это явно огонь + воздух = энергия, земля + земля = песок, песок + огонь = стекло, энергия + стекло = лампочка.

Но я не могу придумать какой-либо способ написать программу для обработки списка и понять это без применения метода грубой силы и перебора каждого элемента и проверки его рецепта.

Это проблема NP? Или я просто не могу это понять?

Answer 1

Как эта программа будет обрабатывать список, создавая лампочку?

Несомненно, вы просто запустите определения в обратном направлении; например

1. Создание лампочку требует 1 энергии + 1 стакан
2. Создание энергии требует 1 огня + 1 воздух

и так далее. Это фактически простая прогулка по дереву.

OTOH, если вы хотите, чтобы компьютер вычислил, что энергия + стекло означает лампочку (а не «blob из расплавленного стекла»), у вас нет шансов решить проблему. Вы, наверное, не смогли заставить 2 игроков согласиться, что энергия + стекло = лампочка!

Answer 2

Вы можете легко смоделировать свою проблему как график и найти решение с любым полным алгоритмом поиска. Если у вас нет опыта, это также поможет изучить automated planning. Я связываюсь с этим текстом, потому что он также содержит введение в сложности и алгоритмы поиска.