Pregunta simple sobre problemas de decisión

8

(Estoy en el medio de mi primer curso cs teórico, así que me disculpo de antemano por lo que probablemente sea una pregunta estúpida).

Entonces, decimos que algún lenguaje L está en P, lo que significa que se puede construir una máquina de Turing que genera un 1 si x está en L y 0 de lo contrario; Además, la máquina funciona en tiempo polinómico. Entiendo esto.

Pero mucha gente dice que hay ciertos problemas en P que no me parecen problemas de decisión; por ejemplo, maximizar una función sujeta a restricciones lineales. ¿Qué significa que la "programación lineal" está en P? ¿Seguramente "encontrar el valor máximo" no es un problema de decisión?

cc.complexity-theory Xodarap
fuente

Respuestas:

16

Tiene razón: formalmente P incluye solo problemas de decisión. Pero muchos problemas de decisión tienen problemas de optimización correspondientes: encuentre el tamaño de la coincidencia más grande en un gráfico, encuentre la longitud del camino más corto de s a t en un gráfico, etc.

A menudo, estos pueden reducirse a problemas de decisión preguntando en su lugar: "¿El gráfico tiene una coincidencia utilizando más de k aristas?" o "¿Hay una ruta s-> t de longitud menor que k?"

Obviamente, si puede resolver el problema de optimización, puede resolver el problema de decisión. Lo contrario también suele ser cierto, hasta factores logarítmicos. Si desea saber el tamaño de la coincidencia más grande en un gráfico, por ejemplo, puede hacer llamadas repetidas a su algoritmo para el problema de decisión "¿El gráfico tiene una coincidencia con más de k aristas?" y hacer una búsqueda binaria en el valor "k". De esta manera, necesitará a lo sumo llamadas log (m), donde m es el número de aristas. Para la mayoría de los problemas hay una reducción análoga.

Aaron Roth
fuente
Para acompañar la respuesta de Aaron, la programación lineal puede formularse como un problema de decisión especificando algún límite, k, que le interese; Este es un truco común. Por ejemplo, ¿existe una asignación de valores a las variables de la función objetivo de modo que satisfaga todas las restricciones lineales Y de modo que la función objetivo tenga un valor mayor o igual (respectivamente, menor o igual que) k? Puede, por ejemplo, decidir esto en tiempo polinómico maximizando / minimizando la función objetivo.
Daniel Apon
Entonces, esencialmente, si sabes "¿hay una solución para X?" está en P, entonces generalmente (pero no siempre) el problema " ¿cuál es la solución para X?" será solucionable en tiempo polinómico?
Xodarap
3
Xodarap: eso es correcto. Por lo general, la capacidad de resolver el problema de decisión rápidamente le permite resolver el problema de búsqueda rápidamente, pero no siempre. Como un famoso contraejemplo: según el teorema de Nash, cada juego de matriz tiene un equilibrio de Nash mixto, por lo que resolver el problema de decisión "¿Tiene este juego un equilibrio de Nash" es trivial? La respuesta es sí. Pero se cree que es difícil -en realidad- encontrar un equilibrio de Nash en un juego genérico.
Aaron Roth
Otro ejemplo de esto es el teorema de Radón. Dados los puntos d + 2 en R ^ d, existe una partición de los puntos en dos conjuntos, de modo que los dos cascos convexos se cruzan. Fácil de verificar una partición candidata, pero difícil de encontrar.
Suresh Venkat
11

Formalmente, la clase de funciones que se pueden calcular en tiempo polinómico se llama FP . La gente suele decir "P" en lugar de "FP", ya que la distinción es simplemente sintáctica y no se producirá una verdadera confusión.

Noam
fuente
8

Ya se ha hecho una pregunta muy similar en el tema " Clase de complejidad FNP ". Allí, el interrogador esencialmente preguntó la diferencia entre las clases de complejidad NP y FNP. Usted está preguntando la diferencia entre las clases de complejidad P y FP. En resumen, P y NP son clases de decisión, mientras que las versiones "F" (FP y FNP) son clases de función. Para obtener más información, consulte el tema citado anteriormente.

MS Dousti
fuente
7

Los problemas que requieren una solución pueden convertirse en problemas de decisión si hay alguna forma de medir qué tan buena es una solución. La versión de decisión especifica que cualquier solución debe ser mejor que algún valor umbral. Por ejemplo, la versión de decisión de PROGRAMACIÓN LINEAL se obtiene preguntando si el programa lineal es factible.

András Salamon
fuente
Ah, en realidad no soy consciente de esto: ¿es más común decidir si existe alguna solución factible que decidir si existe una solución factible de cierto valor?
Daniel Apon
1
CX≥BXCB−CX≤−BCX≥B