Problemas NP Inteligencia Artificial

Por: Guillermo Arturo González

Villagómez y Joel Raúl López Saucedo

Según Alan Turing, si durante el intercambio entre una computadora y el usuario, este último cree que está intercambiando con otro humano, se considera que el sistema es inteligente.

Breve Introducción a IA

Se considera, que la solución de un problema abarca un razonamiento muy complejo, el cual, requiere generar esfuerzos para llegar al fin de la interrogante.

Breve Introducción a IA

Existen 4 diferentes formas de resolución de problemas.

Entrando en materia:

1. Aplicación de una fórmula explícita que da la solución

Entrando en materia:

2. Uso de una definición recursiva.

Entrando en materia:

3. Uso de un algoritmo que converge a la solución

Entrando en materia:

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

Entrando en materia:

una manera sencilla de explicar esto es de la siguiente manera:

Problema:comprobar si el número X es la raíz cuadrada del número Z

Una breve aplicación

Se puede solucionar de las siguientes maneras:.-Calculando la raíz de Z y comprobando con X (proceso lento y engorroso).-Elevando al cuadrado a X y compararlo con Z (simple multiplicación de X*X

Una breve aplicación

Lo que se puede concluir es que en algunos problemas es más fácil comprobarlos que realizarlos

Una breve aplicación

Cuando el algoritmo requiere tiempo polinomial para dar un resultado se dice que el problema es de clase P

Cuando no se conoce un algoritmo de solución polinomial, aunque sea posible, los problemas son de clase NP

Con los problemas de clase NP, dada una solución comprobar en tiempo polinomial si su costo es mejor que un determinado valor

De los problemas de clase NP son los que se encargan los métodos de solución de la Inteligencia Artificial.

Problemas NP-completo (ó Co-NP):contiene los problemas más difíciles de NP, en el sentido de que cuestan más tiempo polinómico que un problema NP “sencillo”

Tipos de Problemas NP

Importancia de Co-NP:se dice que esta clase es importante ya que si se desea conseguir la forma logarítmica de un problema NP, solucionando uno Co-NP se solucionan todos los problemas NP relacionados al problema que se desea resolver.

Tipos de Problemas NP

#P es el conjunto de problemas de conteo correspondientes a los problemas de decisión en NP

Tipos de Problemas NP