Is this an NP problem?

Question

first off I'm going to say I don't know a whole lot about theory and such. But I was wondering if this was an NP or NP-complete problem. It specifically sounds like a special case of the subset sum problem.

Anyway, there's this game I've been playing recently called Alchemy which prompted this thought. Basically you start off with 4 basic elements and combine them to make other elements.

So, for instance, this is a short "recipe" if you will for making elements

fire=basic element
water=basic element
air=basic element
earth=basic element
sand=earth+earth
glass=sand+fire
energy=fire+air
lightbulb=energy+glass

So let's say a computer could create only the 4 basic elements, but it could create multiple sets of the elements. So you write a program to make any element by combining other elements. How would this program process the list the create a lightbulb?

It's clearly fire+air=energy, earth+earth=sand, sand+fire=glass, energy+glass=lightbulb.

But I can't think of any way to write a program to process a list and figure that out without doing a brute force type method and going over every element and checking its recipe.

Is this an NP problem? Or am I just not able to figure this out?

Answer 1

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

Surely you just run the definitions backwards; e.g.

1. Creating a lightbulb requires 1 energy + 1 glass
2. Creating an energy requires 1 fire + 1 air

and so on. This is effectively a simple tree walk.

OTOH, if you want the computer to figure out that energy + glass means lightbulb (rather than "blob of molten glass"), you've got no chance of solving the problem. You probably couldn't get 2 gamers to agree that energy + glass = lightbulb!

Answer 2

You can easily model your problem as a graph and look for a solution with any complete search algorithm. If you don't have any experience, it might also help to look into automated planning. I'm linking to that text because it also features an introduction on complexity and search algorithms.