È questo un problema NP?

Question

Prima di tutto ho intenzione di dire che non so molto a proposito la teoria e così via. Ma mi chiedevo se questo è stato un problema NP o NP-completo. Suona specificamente come un caso particolare del problema sottoinsieme somma.

In ogni caso, non c'è questo gioco ho giocato di recente chiamato alchimia che ha spinto questo pensiero. Fondamentalmente si inizia con 4 elementi di base e combinarle per fare altri elementi.

Così, per esempio, questo è un breve "ricetta", se volete per fare gli elementi

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

Quindi diciamo che un computer potrebbe creare solo i 4 elementi di base, ma potrebbe creare più insiemi di elementi. Quindi scrivere un programma per fare qualsiasi elemento mediante la combinazione di altri elementi. Come questo programma di elaborare l'elenco Crea una lampadina?

E 'chiaramente il fuoco + acqua = energia, terra + terra = sabbia, sabbia + fuoco = vetro, energia + vetro = lampadina.

Ma non riesco a pensare a un modo per scrivere un programma per elaborare un elenco e la figura che fuori senza fare un metodo di tipo forza bruta e andando oltre ogni elemento e controllando la sua ricetta.

E 'questo un problema NP? O sono solo in grado di capirlo?

Answer 1

  

Come potrebbe questo processo programma di lista il creare una lampadina?

Sicuramente basta eseguire le definizioni all'indietro; per esempio.

1. La creazione di una lampadina richiede 1 energia + 1 bicchiere
2. La creazione di un'energia richiede 1 fuoco + 1 aria

e così via. Questa è effettivamente una semplice passeggiata albero.

OTOH, se si desidera che il computer per capire che significa energia + vetro lampadina (piuttosto che "blob di vetro fuso"), hai alcuna possibilità di risolvere il problema. Probabilmente non poteva ottenere 2 giocatori ad accettare che l'energia + vetro = lampadina!

Answer 2

Si può facilmente modellare il problema sotto forma di grafico e cercare una soluzione con qualsiasi algoritmo di ricerca completa. Se non si dispone di alcuna esperienza, potrebbe anche aiutare a guardare in automatizzata pianificazione . Sto collegando a quel testo perché è dotato anche un'introduzione sulla complessità e algoritmi di ricerca.