Derechos De Los Delincuentes

Problemas de Clase P y NP

Por Jonathan León Sepúlveda

Rut:17.771.116-0

Hoy en día nadie puede negar que el estilo de vida de toda persona que se haga llamar “civilizada” gira en torno a la informática. Ya sea por una calculadora, un GPS o un teléfono móvil, la continua y creciente demanda de estas tecnologías han llevado al desarrollo constante de estas con el fin de responder a las necesidades cada vez más exigentes de los consumidores. Para esto se han ido desarrollando y perfeccionando desde hace décadas, una infinidad de algoritmos con distintos propósitos para implementarse en las computadoras.

Todo comenzó con la invención de las Máquinas de Turing en 1936, las cuales son modelos teóricos de Computadoras que hasta el día de hoy se usan.

Una Maquina de Turing es un modelo formal del concepto de algoritmo que podemos imaginar como un dispositivo capaz de leer/escribir símbolos de/en una cinta, y de desplazarse por la misma (o hacer que la cinta se desplace, que tanto da una cosa como la otra). La cinta la podemos imaginar como de longitud ilimitada, y dividida en casillas, en cada una de las cuales puede haber un símbolo. La Maquina se halla en todo momento en un cierto estado interno (de entre un cierto conjunto de estados posibles) y dispone de una función de transición interna que le dice qué debe escribir, cómo debe moverse, y cómo debe cambiar el estado interno en función del estado actual y de lo que esté leyendo en cada momento de la cinta. La definición de la MT es completa si indicamos el alfabeto A que contiene a todos los símbolos que se pueden leer/escribir, el conjunto de estados posibles Q, el estado inicial q0, y la función de transición d. El funcionamiento de la MT termina en el momento que se alcanza un cierto estado de parada. Los contenidos iniciales de la cinta corresponden a la entrada del algoritmo, y los contenidos finales a su salida.

Sin embargo para resolver un problema determinado se requería de una cierta cantidad de tiempo y espacio (memoria). Fue así como nació la Teoría de la Complejidad Computacional, que se centra en la clasificación de los problemas computacionales de acuerdo a su dificultad inherente, y en la relación entre dichas clases de complejidad.

Se dice que un problema es “inherentemente difícil” si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. Entre otros tantos fines, uno de los roles de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede hacer en una computadora y qué no en base a su tiempo de ejecución. Esto se conoce como Tiempo Polinómico.

En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico.

Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por N casas necesita menos de 50N^2+N segundos, entonces el problema es resoluble en un "tiempo polinómico".

Una de las problemáticas sin resolver de la Teoría de la Complejidad Computacional es la relación entre P y NP (polinómico y no-polinómico). La Interrogante es: ¿P=NP? Esta interrogante nace de la base de que un problema NP “sencillo”, es computable, pero la cosa cambia cuando se trata de variables más complejas.

Entonces, si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente?

...