Complejidad de los problemas de decisión
Un problema de decisión comprende dos partes: un dato del problema y una pregunta cuya respuesta es SI o NO
Problemas de decisión clásicos:
SAT:
dato: un conjunto V de variables booleanas y un conjunto C de cláusulas sobre V
pregunta: existe una afectación de las variables que haga verdadera todas las cláusulas?
TSP:
dato: un grafo G=(X,U) valuado y un número B
pregunta: Existe un circuito hamiltoniano de G de valor menor a B?
PARTICION:
dato: un conjunto A={ai /i?I} de n números enteros
pregunta: ¿existe una partición de A en dos sub-conjuntos A1 y A2 de igual peso?:
?ai= ?ai = !/2* ?ai ?
i?I1 i?I2 i?I
KNAPSACK:
dato: un conjunto de n parejas (bi,ci) de enteros y dos constantes K1 y K2
pregunta: Existe un subconjunto J de I /:
?bi=? K1 y ?ci ? K2 ?
i?J i?J
CLIQUE:
dato: un grafo G=(X,U) y un entero positivo J
pregunta: G contiene un clique (subgrafo completo de G) de tamaño J?
TRIPARTICION:
dato: un conjunto A={ai /i?I} de 3q números enteros con ?ai= qB y para todo i, B/4 ? ai ? 3B/4
i?I
pregunta: ¿existe una partición de A en q sub-conjuntos de cardinalidad 3 y peso B?:
ILP:
dato: Una matriz A (m,n) con valores enteros, una matriz línea c con valores enteros de orden n, una matriz columna b de orden m y un número entero B,
pregunta: Hay una matriz columna x con valores enteros / Ax ?b y cx ?B?
Lenguajes y Problemas de decisión
Codificación: permite asociar a todo enunciado de un problema una palabra x definida sobre un alfabeto X (x ?X*) . A todo problema de decisión se le asocia un lenguaje L ? X*, que está formado por un conjunto de palabras para las cuales la respuesta es SI.
Clase NP
Máquinas de Turing no determinísticas (MTND).
Def: la clase NP es el conjunto de lenguajes reconocidos polinomialmente por una MTND:
L ? NP si existe una MTND y un polinomio P/ x ?L sii la MTND termina en el estado SI para el dato x en tiempo finito y
T(x) ? P(x) (T(x)=duración del cálculo en la MTND)
Los problemas de decisión clásicos pertenecen a NP
Para verificar que un problema de decisión es NP, una vez fijado los valores de una potencial solución, alcanza con que la verificación se realice en tiempo polinomial.
Reducción polinomial
Def: Se dice que un problema ?1 se reduce polinomialmente a otro ?2 : ?1??2, si ?1es polinomial o si existe un algoritmo polinomial que construye a partir de un dato D1 de entrada de ?1 uno D2 de ?2 , tal que la respuesta para D1 es SI, si y solamente si la respuesta para D2 es SI.
Prop: si existe un algoritmo polinomial para resolver ?2 entonces existirá un algoritmo polinomial para resolver ?1 . Se dice entonces que ?2 es mas difícil que ?1
La reducción polinomial es un preorden sobre NP: es reflexiva y transitiva. Se puede definir entonces una relación de equivalencia y una relación de orden para las clase s de equivalencia asociadas: ?1 es equivalente a ?2 si: ?1??2 y ?2??1
La subclase más fácil de NP: la clase P
Def: los problemas NP-completos: Cook demostró que todo problema de NP se reduce polinomialmente a SAT, entonces SAT es un problema más difícil que todo problema de NP. Como SAT pertenece a NP, NP contiene una subclase de problemas más difíciles , los NP-completos
Los problemas de decisión clásicos son NP-completos
Para demostrar que un problema ?2 es NP-completo alcanza con verificar que pertenece a NP y de encontrar un problema ?1 , probado NP-completo y demostrar que ?1 ? ?2
Ejemplos :
1) Problema de una máquina:
dato: I={ n tareas independientes, no divisibles},
J={(pi,ri,di) ?i?I} /
pi=duración, ri = fecha de disponibilidad,di=fecha de finalización
pregunta: hay un orden de ejecución de estas n tareas sobre una máquina que respete las fechas de disponibilidad y finalización para todas las tareas?
2) Problema de dos máquinas:
dato: I={ n tareas independientes, no divisibles},
J={pi, ?i?I} y un número B
pregunta: hay un orden de ejecución de estas n tareas sobre dos máquinas, de duración inferior a B?
Prop: Los problemas de una y dos máquinas
son NP-completos
Se demuestra probando que:
a) los Problemas de una y dos máquinas son de NP
b) PARTICION se reduce polinomialmente al problema de una máquina
b) PARTICION se reduce polinomialmente al problema de dos máquinas
Conjetura fundamental: P?NP
La duración de los algoritmos es función de la longitud de los datos de entrada. Para codificar un número entero ai, alcanza con ?log ai? bits,
2
Def: un algoritmo es de complejidad pseudo-polinomial si es polinomial para una codificación en base 1 de los datos de entrada. (la codificación en base 1 de ai necesita ai bits)
Def: Problemas NP en sentido fuerte: si son NP -completos y si la existencia de un algoritmo pseudo-polinomial para resolverlo, implica la existencia de uno polinomial.
Problemas de búsqueda
Para muchos problemas no es suficiente probar la existencia de una solución, es necesario encontrarla
Def: Un problema de búsqueda ? consiste en un conjunto de datos D? y para cada dato D? D? , un conjunto de soluciones S?(D). Un algoritmo resuelve un problema de búsqueda ? si, ?D?D?, calcula un elemento de S?(D) , para el caso S?(D)?? y de lo contrario devuelve ?.
A cada uno de los problemas de decisión clásicos le corresponde un problema de búsqueda
Problemas de optimización
Un problema de optimización se obtiene a partir de un problema de búsqueda, asociándole a cada solución un valor y buscando la solución de valor óptimo.
Ejemplo: En TSP-optimización se buscará el circuito hamiltoniano de largo mínimo.
==> Un problema de optimización es un problema de búsqueda en el cual la función económica juega un rol particular, ya que establece un criterio de búsqueda: S?(D) se restringe al conjunto de soluciones óptimas
Reducción de Turing
Def: Se dice que un problema de búsqueda ?1 se reduce polinomialmente a otro ?2 por la reducción de Turing: ?1?T?2, si para resolver ?1 existe un algoritmo A1 que utiliza como subprograma un algoritmo A2 que resuelve ?2 y tal que la complejidad de A1 es polinomial cuando se evalúa arbitrariamente cada llamado a A2 como una constante.
Prop: si A2 polinomial => A1 polinomial
La reducción de Turing es también un preorden que permite comparar problemas de búsqueda.
Página siguiente  |