3.
Complejidad de los problemas
1. Explique la definición formal de un problema
Lo primero que debe hacerse al momento de realizar el diseño de un programa para dar solución a un problema es realizar una descripción formal, y de esta manera abordar mejor el problema. Esta descripción formal debe hacerse de manera manual y se desarrollada de la manera más estudiada posible.
Hay problemas que por ser artificiales y estructurados son fáciles de especificar. Otros problemas naturales, como por ejemplo la comprensión del lenguaje, no son tan sencillos de especificar.
Para producir una especificación formal de un problema se deben definir:
Un estado es la representación de un problema en un instante dado.
2. Mediante una presentación explique en qué consiste y de ejemplos de las clases P, NP y NP completo.
1. Explique la definición formal de un problema
Lo primero que debe hacerse al momento de realizar el diseño de un programa para dar solución a un problema es realizar una descripción formal, y de esta manera abordar mejor el problema. Esta descripción formal debe hacerse de manera manual y se desarrollada de la manera más estudiada posible.
Hay problemas que por ser artificiales y estructurados son fáciles de especificar. Otros problemas naturales, como por ejemplo la comprensión del lenguaje, no son tan sencillos de especificar.
Para producir una especificación formal de un problema se deben definir:
- espacio de estados válidos;
- estado inicial del problema;
- estado objetivo o final;
- reglas que se pueden aplicar para pasar de un estado a otro.
Un estado es la representación de un problema en un instante dado.
2. Mediante una presentación explique en qué consiste y de ejemplos de las clases P, NP y NP completo.
3. Señale y explique 3 problemas NP. ¿Por qué se consideran
problemas NP?
Dada la formulación, es fácil exhibir un verificador y un certificado. Un certificado es un camino hamiltoniano, y se puede fácilmente comprobar linealmente que un camino s ́ı es hamiltoniano. Ahora, no se conoce algoritmo (determinista) polinomial para encontrar uno (por ejemplo lo usado por encontrar un camino cualquiera no funciona aquí).
Ya conocemos una forma posible de descomponer un número n en sus factores: probar a dividirlo por todos los números enteros positivos comprendidos entre 2 y la raíz de n. Pero cuando hablamos de un número de tamaño 1024 bits, este método es computacionalmente impracticable. Por supuesto, a lo largo del tiempo los matemáticos han inventado otros métodos de factorización más eficientes, pero ninguno ha conseguido un algoritmo con un orden de complejidad que permita factorizar en un tiempo razonable números de tamaños como los empleados en RSA actualmente, aun con la potencia computacional disponible hoy en día.
De hecho el problema de la factorización de enteros se considera que es un problema de clase NP, es decir, un problema para el que existe uno o más algoritmos que lo resuelven, pero ninguno de los algoritmos conocidos se ejecutan en un tiempo polinomial (que pueda ser expresado polinómicamente en función del tamaño de los datos de entrada), y por lo tanto son ineficientes o intratables para datos de entrada muy grandes.
- Acomodar los números del 1 al 4 (24 maneras) te puede llevar tal vez un minuto, pero acomodar los números del 1 al 8 (40320 maneras) te llevará mucho más, a pesar de que 8 es apenas dos veces mayor que 4. Este tipo de problemas llega el momento que se consideran insolubles porque para resolverlos necesitarías más tiempo del que hay en el Universo.
- En un grafo orientado, existe un camino entre dos nodos a y b que pase por todos los nodos una y una sola vez (camino hamiltoniano)?
Dada la formulación, es fácil exhibir un verificador y un certificado. Un certificado es un camino hamiltoniano, y se puede fácilmente comprobar linealmente que un camino s ́ı es hamiltoniano. Ahora, no se conoce algoritmo (determinista) polinomial para encontrar uno (por ejemplo lo usado por encontrar un camino cualquiera no funciona aquí).
- El problema de la factorización de números grandes
Ya conocemos una forma posible de descomponer un número n en sus factores: probar a dividirlo por todos los números enteros positivos comprendidos entre 2 y la raíz de n. Pero cuando hablamos de un número de tamaño 1024 bits, este método es computacionalmente impracticable. Por supuesto, a lo largo del tiempo los matemáticos han inventado otros métodos de factorización más eficientes, pero ninguno ha conseguido un algoritmo con un orden de complejidad que permita factorizar en un tiempo razonable números de tamaños como los empleados en RSA actualmente, aun con la potencia computacional disponible hoy en día.
De hecho el problema de la factorización de enteros se considera que es un problema de clase NP, es decir, un problema para el que existe uno o más algoritmos que lo resuelven, pero ninguno de los algoritmos conocidos se ejecutan en un tiempo polinomial (que pueda ser expresado polinómicamente en función del tamaño de los datos de entrada), y por lo tanto son ineficientes o intratables para datos de entrada muy grandes.