Muchos problemas de difícil solución algorítmica pueden resolverse tratándolos como un problema de búsqueda en un espacio de estados. Un espacio de búsqueda consta de un estado inicial, estados intermedios y estados finales que señalan que se ha alcanzado el éxito en la resolución del problema.[4]

El espacio de estados puede representarse mediante una estructura arborescente o un grafo. En el caso concreto de un programa definido P y un objetivo definido G, el conjunto de toda las posibles derivaciones SLD para P U {G} se puede representar como un árbol.