## 3.3.1 PROBLEMAS DE DECISIÓN Y PROBLEMAS DE OPTIMIZACIÓN

Problemas de decisión

Un problema de decisión C es NP-completo si:

1. C es un problema NP, y
2. Todo problema de NP se puede transformar polinómicamente en C.

Se puede demostrar que C es NP demostrando que un candidato a solución de C puede ser verificado en tiempo polinómico. Una transformación polinómica de L en C es un algoritmo determinista que transforma instancias de l ∈ L en instancias de c ∈ C, tales que la respuesta a c es positiva si y sólo si la respuesta a l lo es.

Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP.
Esta definición fue propuesta por Stephen Cook en 1971. Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo. Desde entonces se ha demostrado que miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros problemas para los que ya se había demostrado su pertenencia a NP-completo; muchos de esos problemas aparecen en el libro de Garey and Johnson's de 1979 Computers and Intractability: A Guide to NP-completeness. Un problema que satisface la segunda condición pertenece a la clase NP-duro independientemente de que satisfaga la primera.

Problemas de Optimización

Los problemas de optimización son aquellos donde buscamos el máximo o el mínimo de una función donde existen o no un conjunto de restricciones. Sin embargo, un problema de optimización combinatoria puede también ser formulado de manera más relajada como sigue:

Dado un problema de optimización, podemos encontrar el costo de la solución óptima.

Se sabe que dado un problema de optimización, se puede definir un problema de decisión asociado a él, esto es, una pregunta que puede ser contestada por si o no. Por otro lado, varios problemas computacionales bien conocidos son problemas de decisión. Entre los problemas de decisión se pueden mencionar por ejemplo:

• El problema de paro (Halting Problem): dado un algoritmo y su entrada, ¿Parará éste alguna vez?.
• El problema de satisfactibilidad: dada una fórmula booleana, ¿Es ésta satisfactible?.
• El problema del circuito Hamiltoniano: dado un grafo G, ¿Hay un circuito en G que visite todos los nodos exactamente una vez?.

La definición de problema de decisión a partir del problema de optimización permite estudiar ambos tipos de problemas de una manera uniforme.

Además, como se ha puntualizado que un problema de decisión no es más difícil que el problema de optimización original, cualquier resultado negativo probado sobre la complejidad del problema de decisión será aplicable al problema de optimización también.

Se está interesado en clasificar los problemas de decisión de acuerdo a su complejidad. Se denota por P a la clase de problemas de decisión que son polinomialmente acotados, esto es, la clase de problemas de decisión que pueden ser solucionados en tiempo polinomial. La clase P puede ser definida muy precisamente en términos de cualquier formalismo matemático para algoritmos, como por ejemplo la Máquina de Turing.

Se puede decir que P es la clase de problemas de decisión relativamente fáciles, para los cuales existe un algoritmo que los soluciona eficientemente. Para una entrada dada, una "solución" es un objeto (por ejemplo, un grafo coloreado) que satisface el criterio en el problema y justifica una respuesta afirmativa de si. Una "solución propuesta" es simplemente un objeto del tipo apropiado, este puede o no satisfacer el criterio. Informalmente se puede decir que NP es la clase de problemas de decisión para los cuales una solución propuesta dada para una entrada dada, puede ser chequeada rápidamente (en tiempo polinomial) para ver si ésta es realmente una solución, es decir, si ésta satisface todos los requerimientos del problema.

Una solución propuesta puede ser descrita por una cadena de símbolos a partir de algún conjunto finito. Simplemente se necesita alguna convención para describir grafos, conjuntos, funciones, etc. usando estos símbolos. El tamaño de la cadena es el número de símbolos en ella. Chequear una solución propuesta incluye chequear que la cadena tenga sentido (esto es, que tenga una sintaxis correcta) como una descripción del tipo de objeto requerido, también como chequear que ésta satisface el criterio del problema.

Problemas de decisión vs Problemas de Optimización

Muchos problemas de interés son problemas de optimización, en los que cada solución factible tiene un valor asociado, y deseamos encontrar una solución factible con el mejor valor.

Por ejemplo, en un problema que llamamos CORTOCIRCUITO-RUTA:
Se nos da un gráfico de un gráfico no dirigido, y deseamos hallar un par sin usar el menor número de bordes. En otras palabras, SHORTEST-PATH es el problema de ruta más corta de un solo par en un gráfico no ponderado, no dirigido. NP-completos se aplica directamente no a problemas de optimización, sino a problemas de definición, en los que la respuesta es simplemente "sí" o "no" (o, más formalmente, "1" o "0"). Aunque NP-completos los problemas se limitan al ámbito de los problemas de decisión; podemos aprovechar una relación conveniente entre los problemas de optimización y los problemas de decisión. Por lo general, podemos emitir un problema de optimización dado como un problema de decisión relacionado mediante la imposición de un límite en el valor que se optimizará. Por ejemplo, un problema de decisión relacionado con SHORTEST-PATH es PATH: dado un gráfico dirigido, vértices y una integridad.

¿Existe una ruta desde la autoconstrucción en la mayoría de las visitas?

La relación entre un problema de optimización y su problema de decisión relacionado funciona en a nuestro favor cuando tratamos de demostrar que el problema de optimización es "difícil". Esto se debe a que el problema de decisión es en cierto sentido "más fácil", o al menos "no más intenso". Como ejemplo específico, podemos resolver PATH resolviendo SHORTEST- PATH y luego comparar el número de aristas en el camino más corto encontrado con el valor del parámetro de decisión parámetro. En otras palabras, si un problema de optimización es fácil, su problema de decisión relacionado también es fácil. Expuesto de una manera que tiene más relevancia para la integridad de NP, si podemos proporcionar evidencia de que un problema de decisión es difícil, también proporcionamos evidencia de que su problema de optimización relacionado es difícil. Por lo tanto, a pesar de que restringe la atención a los problemas de decisión, la teoría de la completitud del NP a menudo también tiene implicaciones para los problemas de optimización.

###