Según Alan Turing "…si durante el intercambio entre una computadora y el usuario este último cree que está intercambiando con otro humano, entonces se dice que el programa es inteligente…"

La solución de problemas puede considerarse una forma de razonamiento muy compleja que requiere la generación y asimilación de nuevas estructuras de memoria a fin de contestar una interrogante. Es la actividad mental de encontrar una solución a un problema. En el contexto del procesamiento de la información el enfoque dado a la solución de problemas ha sido tratar de trazar la gráfica de la secuencia de eventos desde la formulación del problema hasta su solución final; o sea, tratar de comprender el proceso que interviene para derivar una solución.

Hay cuatro vías principales para encontrar la solución a un problema dado:

• La aplicación de una fórmula explícita que da la solución.

• El uso de una definición recursiva.

• El uso de un algoritmo que converge a la solución.

• La aplicación de otros procesos, en particular la prueba y error.

Siempre que sea posible el primer método es el mejor. Por ejemplo, encontrar los ceros de un polinomio de segundo grado. En este caso la complejidad de hallar la solución es constante, O(1). El método recursivo es computacionalmente muy costoso. Por ejemplo, el cálculo de los números de Fibonacci se formula como:

F(n) = F(n-1) + F(n-2)

F(2) = F(1) = 1

es decir:

procedure F(n);

begin

if n > 2

then F(n):= F(n-1) + F(n-2)

else F(n):= 1

end;

En este caso la complejidad es O[F(n)], quiere decir la complejidad crece exponencialmente. Una alternativa para reducir este costo es transformarlo en un proceso iterativo:

procedure Fibonacci(n);

begin

I := 2; U := 1; V := 1;

while I ( n do

begin

I := I + 1;

W := U;

U := U + V;

V := W

end;

return U;

end

Ahora la complejidad es O(n) el lugar de O[F(n)]. Un buen algoritmo puede tener complejidad polinomial.

Las tres primeras vías son las usadas en los programas de computadoras tradicionales; ellos incluyen el desarrollo de un modelo matemático o lógico adecuado que describe un dominio o una parte de él. La solución al problema se deriva del uso de ese modelo. Con la existencia de este modelo se puede hallar una secuencia estructurada de paso que garantiza encontrar una solución al problema en una longitud finita de tiempo. Tales procedimientos son llamados algoritmos y ellos forman la base para sistemas de software convencional.

La cuarta vía es la utilizada para problemas en los cuales no hay una solución algorítmica conocida o es tan compleja que no es posible una implementación computacional conocida práctica. Sin embargo, estos problemas son resueltos por los humanos a pesar de su capacidad de procesamiento "inferior". Por ejemplo, el problema del Viajero vendedor cae en esta ultima clase de problemas.

Existen problemas combinatorios para los cuales no se conocen algoritmos de resolución que no sean otros que aquellos que producen una explosión del tiempo de cálculo (exponencialmente) al aumentar el tamaño del problema. Por el contrario, para otros problemas combinatorios, como por ejemplo, el denominado problema de asignación consistente en acoplar n trabajadores con n puestos de trabajo sabiendo el costo cij de emparejar el trabajador i con el puesto j, sí existen algoritmos que sólo crecen en tiempo polinomialmente con el tamaño del problema; para el problema de asignación el denominado Algoritmo Húngaro necesita un tiempo de calculo que crece simplemente según n3.

Matemáticamente se trató de caracterizar ambos tipos de problemas. Aquellos para los cuales se conocen algoritmos que necesitan un tiempo polinomial para ofrecer una solución óptima se dice que pertenecen a la clase P y se consideran que son solubles eficientemente. Por otra parte, en la clase NP están incluidos todos los problemas para los que no se conoce un algoritmo de solución polinomial, aunque si sea posible, dada una solución, comprobar en tiempo polinomial si su costo es mejor que un determinado valor. Un ejemplo de problema NP es el problema de la Mochila (seleccionar entre un conjunto de n productos, cada uno con un valor ci y un volumen vi, aquellos que quepan en un recipiente de volumen V y que tengan el mayor valor posible).

De esta clase de problemas es de los que se ocupan los métodos de solución de problemas de la Inteligencia Artificial. La razón está dada por la necesidad de disponer de herramientas que permitan ofrecer soluciones (aunque no sean óptimas) a problemas reales. Esto queda evidenciado claramente en campo empresarial. Los directivos por lo general desean mejorar sus operaciones del modo más rápido, barato y simple posible sin importarles realmente si ése es el modo óptimo. Estos algoritmos, aunque no optimizan una función objetivo, ofrecen soluciones factibles, es decir satisfacen las restricciones del problema, las cuales se acercan al valor óptimo en un tiempo de cálculo razonable. En última instancia puede ser útil encontrar una solución independientemente de su lejanía a una solución óptima.