Page 178 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

tesis de computabilidad secuencial

En la tabla 1.4 se describió la diferencia entre algoritmos que utilizaban cantidades polinomiales (n )
c
y exponencial (c ). Los algoritmos polinomiales tienden a ser factibles para tamaños razonables de
n
datos de entrada. Los algoritmos exponenciales tienden a exceder los recursos disponibles aun
tratándose de cantidades pequeñas de datos de entrada. Uno de los objetivos de la teoría de com-
plejidad es mejorar esta clasificación de los algoritmos y, por ende, la comprensión de la diferencia
entre problemas factibles y no factibles.

Si un algoritmo se construye tomando dos algoritmos factibles y colocándolos en forma secuencial
uno después del otro, el algoritmo así construido debe ser factible. De manera semejante, si algún
algoritmo factible se reemplaza por una llamada a un módulo que representa a un segundo algoritmo
factible, el nuevo algoritmo combinado también debe ser factible. Esta propiedad de cerradura en
realidad se cumple para algoritmos de tiempo polinomial.
Cualquier algoritmo que se ejecuta en tiempo polinomial en una computadora puede correr en tiem-
po polinomial en cualquier otra. De ahí que tenga sentido hablar de algoritmos de tiempo polinomial
en forma independiente de cualquier computadora específica. Una teoría de algoritmos factibles
basada en el tiempo polinomial es independiente de la máquina.

La creencia de que todas las computadoras secuenciales razonables que se llegan a crear tienen
tiempos de ejecución relacionados polinomialmente recibe el nombre de tesis de computación se-
cuencial. Esta puede compararse con la tesis de Curch-Turing. Es una versión más fuerte de esta,
pues afirma no solo que todos los problemas computables son los mismos para todas las computa-
doras, sino también que todos los problemas computables factibles son los mismos para todas las
computadoras.

problemas Np
Esta sección contiene lo que tal vez fue el desarrollo más importante en investigación de algoritmos
en la década de 1970, no solo en ciencias de la computación, sino también en ingeniería eléctrica,
en investigación de operaciones y en otras áreas relacionadas.

Una idea importante es la distinción entre un grupo de problemas cuya solución se obtiene en tiempo
polinomial y un segundo grupo de problemas cuya solución no se obtiene en tiempo polinomial.

Definición formal de NP
Un problema de decisión £ está en NP si y solo si existe un polinomio P y una máquina de Turing M ,
u
tales que para toda cadena posible de entrada X de longitud n, existe una cadena u cuya longitud es
como máximo p(n) y M (x) = 1, es decir, la máquina de Turing definida por u verifica afirmativamente
u
el problema £. Esta cadena u se conoce como el certificado de £. En términos más profanos, u es el
programa que verifica afirmativamente a £ (Areán Álvarez, 2014).

172