Resumen AYDA2
Problemas Difíciles:
Procedimiento: secuencia de pasos elementales, precisos, que pueden ejecutarse para
resolver una tarea.
Algoritmo: es un procedimiento efectivo, es decir un procedimiento que tiene finitud.
Programa: Los programas son una forma computacional de expresar algoritmos (más
precisamente colecciones de algoritmos), pero no toda ejecución de un programa es un
procedimiento efectivo.
Un problema puede tener soluciones algorítmicas pero no ser computacionalmente
tratable, es decir no admite algoritmos razonables
Problemas de Decisión: Decidibles/Indecidibles
Informalmente, los problemas de optimización son un tipo general de problemas en los
que se desea elegir el mejor de un conjunto de elementos.
Problemas de Optimización: Solubles/Insolubles
Un problema de decisión puede ser formulado de manera tal que dada una entrada
requiere una respuesta simple: “si” o “no”, “true” o “false”.
Problemas de decisión vs Problemas de Optimización
La clasificación de problemas de decisión puede basarse en modelos de procedimientos
más simples que los que requeriría una clasificación de problemas de optimización. Por
ejemplo, pueden basarse en autómatas “reconocedores” como la máquina de Turing.
Para todo problema de optimización se puede construir una versión de un problema de
decisión del mismo “grado de dificultad”.
Clasificación de problemas decidibles
P-tiempo
• La clase de problemas de decisión de complejidad temporal polinomial.
• La clase de lenguajes que pueden ser reconocidos por Máquinas de Turing
determinísticas de complejidad temporal polinomial.
NP-tiempo
• La clase de lenguajes que pueden ser reconocidos por Máquinas de Turing no
determinísticas de complejidad temporal polinomial.
• Nondeterministic Polinomial
NP-Completo
Los problemas NP-Completo son los “más difíciles” en NP-tiempo dado que si existiese un
algoritmo de complejidad temporal polinomial para un problema de la clase NP-Completo, luego
existiría un algoritmo de complejidad temporal polinomial para TODO problema perteneciente a
NP-tiempo. Si existiese un algoritmo polinomial para un problema NP-completo, podríamos
resolver cualquier problema en NP-tiempo en un tiempo polinomial, luego P = NP.
Se conjetura que P ≠ NP.
NP-Hard
Siempre es posible construir una versión de decisión para un problema de optimización que tenga
el mismo grado de dificultad.
• Decisión :NP-Completo
• Optimización :NP-Hard
PSPACE
La clase de lenguajes que pueden ser reconocidos por Máquinas de Turing de complejidad espacial
polinomial. Se conjetura que existen problemas PSPACE-completo tal que si uno de ellos está en
NP, PSPACE=NP, o, si uno de ellos está en P, PSPACE= P.
PSPACE-completo
Una fórmula booleana plenamente cuantificada es una fórmula en lógica de primer orden donde
toda variable es cuantificada Se puede generalizar el problema SAT para el problema de la fórmula
booleana cuantificada, un importante problema PSPACE completo.
¿Por qué tratar de resolver problemas en P-tiempo?
No podemos afirmar que todo problema en P-tiempo tiene una solución eficiente.
• Para ciertas instancias y en función de restricciones al tiempo de ejecución, un problema
en P-tiempo puede ser ineficiente.
• Puede estar en P-tiempo y el orden del polinomio ser alto No podemos afirmar que todo
problema en NP-Hard es ineficiente.
• Un problema en NP-Hard puede ser “tratable” para ciertas instancias.
Sin embargo, hay muy buenas razones para buscar soluciones que estén en P-tiempo dado que un
problema que no está en P-tiempo será, en general, muy costoso y probablemente “intratable”.
Un algoritmo para un problema complejo puede construirse combinando algoritmos para
problemas simples. Los algoritmos simples pueden operar sobre las mismas entradas o sobre
entradas calculadas como resultados intermedios de otros problemas simples. Luego, la
complejidad del algoritmo puede ser acotada por suma, multiplicación y composición de
complejidades de otros algoritmos. Los polinomios son cerrados bajo estas operaciones, luego
cualquier algoritmo construido a partir de algoritmos acotados polinomialmente será también un
algoritmo acotado polinomialmente.
Algoritmos aproximados
Si bien no se ha podido demostrar aún que no existen algoritmos eficientes para las clases NP-
completo, PSPACE completo y NP-Hard, desde el punto de vista práctico hay que resolverlos
eficientemente.
• Si las entradas son “pequeñas” podríamos construir algoritmos basados en backtracking
que realicen una búsqueda exhaustiva.
• Sino, podríamos construir soluciones aproximadas, “cercanas” a la mejor solución, a
partir de algoritmos polinomiales.
Algoritmo aproximado
Algoritmo que proporciona una solución aproximada, que si bien no es la óptima, se puede
“medir” cuán cerca está de la óptima.
• Los algoritmos heurísticos y los aproximados no garantizan encontrar la solución óptima
• Los algoritmos aproximados establecen una cota de error.
Supongamos problemas de optimización, en los que cada solución factible tiene un costo positivo
y se pretende obtener una solución cercana a la óptima. Dependiendo del problema, una solución
óptima puede ser definida como el máximo o el mínimo costo de las soluciones factibles. El
problema de optimización puede ser de maximización o minimización.
Un algoritmo aproximado está acotado por ρ(n) si para cualquier entrada de tamaño n, el costo
de la solución del algoritmo para un costo de una solución factible c y un costo c* de una solución
óptima es:
Dependiendo del problema:
a) si el problema es de maximización: c / c* ≤ ρ(n) 0 < c ≤ c* Es decir, Max (c/c*, c*/c) ≤ ρ(n)
b) si el problema es de minimización: c* / c ≤ ρ(n) 0 < c* ≤ c
El factor de aproximación de un algoritmo aproximado nunca es menor que 1, ya que C / C* ≥ 1
implica que C* / C ≥ 1.
• ρ (n)= 1 : El algoritmo produce una solución óptima
Dos veces el óptimo (minimización)
• ρ (n)= 2 : El algoritmo produce una solución cuyo valor es lo sumo La mitad del óptimo (maximización)
• ρ (n)>>1 : Cuanto mayor es el factor de aproximación ρ (n), el algoritmo de aproximación puede
retornar una solución más alejada de la óptima.
Un esquema de aproximación para un problema de optimización es un algoritmo de aproximación
que toma como entrada:
• una instancia del problema,
• Un valor ɛ > 0, tal que para cualquier ɛ fijo, el esquema es un algoritmo de aproximación con
una cota de error relativo ɛ (un algoritmo (1+ ɛ))-aproximado).
Un esquema de aproximación de tiempo polinomial, para cualquier ɛ > 0 fijo, es un esquema que
se ejecuta en un tiempo polinomial en el tamaño n de su entrada.
