Page 186 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 186
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
NP-HARD code generation problems
• Code Generation With Common Subexpressions.
• Implementing Parallel Assignment Instructions (Garey y Johnson, 1975).
La literatura muestra una gran cantidad de problemas NP-difíciles.
cómo simplificar los problemas Np
Una vez que se mostró el tiempo que se tarda en resolverse cualquier problema L del tipo NP-difícil,
nos podríamos inclinar por desechar la posibilidad de que L se pueda resolver en un tiempo polino-
mial determinístico. En este punto, sin embargo, uno puede realizar la siguiente pregunta: ¿podría
uno restringir el problema L a una subclase para poderse resolver en tiempo polinomial determinís-
tico? Se puede observar que colocando las restricciones suficientes sobre un problema NP-difícil (o
definiendo una subclase lo suficientemente representativa), se puede llegar a un problema que se
pueda resolver en un tiempo polinomial, pero la solución tiene un relajamiento y no es el problema
como tal.
Ya que es casi imposible que los problemas NP-difíciles se puedan resolver en tiempo polinomial, es
importante determinar cuáles son las restricciones para relajar dentro de las cuales se pueda resolver
el problema en tiempo polinomial.
una posible máquina no determinística
La computación cuántica es un paradigma de computación distinto al de la computación clásica. Se
basa en el uso de qubits en lugar de bits, lo que da lugar a nuevas puertas lógicas que hacen posi-
bles nuevos algoritmos. Una misma tarea puede tener diferente complejidad en computación clásica
y en computación cuántica, lo que ha dado lugar a una gran expectación, ya que algunos problemas
intratables pasan a ser tratables. Mientras que un computador clásico equivale a una máquina de
Turing, un computador cuántico equivale a una máquina de Turing cuántica.
En 1985, Deutsch presentó el diseño de la primera máquina cuántica basada en una máquina de
Turing. Con este fin enunció una nueva variante de la tesis de Church-Turing, lo que dio lugar al de-
nominado principio de Church-Turing-Deutsch.
180
