¿Por qué no hay algoritmos de aproximación para SAT y otros problemas de decisión?

18

Tengo un problema de decisión NP-completo. Dada una instancia del problema, me gustaría diseñar un algoritmo que genere SÍ, si el problema es factible, y, de lo contrario, NO. (Por supuesto, si el algoritmo no es óptimo, cometerá errores).

No puedo encontrar ningún algoritmo de aproximación para tales problemas. Estaba buscando específicamente SAT y encontré en la página de Wikipedia sobre Algoritmo de aproximación lo siguiente: Otra limitación del enfoque es que se aplica solo a problemas de optimización y no a problemas de decisión "pura" como la satisfacción, aunque a menudo es posible ... .

¿Por qué, por ejemplo, no definimos la relación de aproximación como algo proporcional al número de errores que comete el algoritmo? ¿Cómo resolvemos realmente los problemas de decisión de manera codiciosa y subóptima?

Ribz
fuente
55
Hay algoritmos de aproximación para MAX-SAT.
Yuval Filmus
2
MAX-SAT no es un problema de decisión, ¿no?
Ribz el
15
Los algoritmos de aproximación son siempre para problemas de optimización.
Yuval Filmus el
44
Entonces, básicamente, desea tener un algoritmo que termine rápidamente pero que ocasionalmente se le dé una respuesta incorrecta. Creo que está confundiendo enormemente los problemas al usar términos bien definidos como "algoritmo de aproximación" y "óptimo" aquí. Esos tienen significados muy específicos. Supongo que está buscando una heurística: si actualiza su pregunta con ese término (o comienza de cero con una nueva pregunta para evitar aún más confusión), podría obtener mejores resultados.
AnoE
Si bien esta no es una respuesta completa, explica parte de la razón: existen problemas importantes de SAT para los cuales tener solo el bit bajo incorrecto no es mejor que estar la mitad de los bits incorrectos.
Joshua

Respuestas:

33

Los algoritmos de aproximación son solo para problemas de optimización, no para problemas de decisión.

¿Por qué no definimos la relación de aproximación como la fracción de errores que comete un algoritmo al intentar resolver algún problema de decisión? Debido a que "la relación de aproximación" es un término con un significado estándar bien definido, uno que significa algo más, y sería confuso usar el mismo término para dos cosas diferentes.

Bien, ¿podríamos definir alguna otra relación (llamémosla de otra manera, por ejemplo, "la relación det") que cuantifica el número de errores que comete un algoritmo, para algún problema de decisión? Bueno, no está claro cómo hacerlo. ¿Cuál sería el denominador para esa fracción? O, para decirlo de otra manera: habrá un número infinito de instancias de problemas, y para algunos de ellos el algoritmo dará la respuesta correcta y otros dará la respuesta incorrecta, por lo que terminará con una relación que es "algo dividido por infinito", y eso termina sin sentido o no definido.

Alternativamente, podríamos definir como la fracción de errores que el algoritmo comete, en casos problemáticos de tamaño n . Entonces, podríamos calcular el límite de r n como n , si existe dicho límite. Esto seriarnortenorternortenorteestar bien definido (si existe el límite). Sin embargo, en la mayoría de los casos, esto podría no ser terriblemente útil. En particular, asume implícitamente una distribución uniforme en las instancias problemáticas. Sin embargo, en el mundo real, la distribución real en las instancias problemáticas puede no ser uniforme, a menudo está muy lejos de ser uniforme. En consecuencia, el número que obtiene de esta manera a menudo no es tan útil como podría esperar: a menudo da una impresión engañosa de lo bueno que es el algoritmo.

Para obtener más información sobre cómo las personas lidian con la intractabilidad (dureza NP), eche un vistazo a Cómo lidiar con la intratabilidad: problemas NP-completos .

DW
fuente
3
+1. Pero el último punto no es sólido, se podría argumentar que puede definir la relación de aproximación como el límite a medida que n llega al infinito del número de errores que el programa comete al ingresar la longitud n sobre el número de cadenas de longitud n. Por supuesto, esto no resulta útil, ya que a menudo un programa simple que solo muestra "SÍ" (o "NO") logra una buena proporción (¡a veces incluso 1!).
aelguindy
1
@det, esa es una pregunta separada, una que debe hacer por separado (después de leer sobre ella en libros de texto estándar o recursos en línea). Preferimos que haga solo una pregunta por publicación.
DW
1
@aelguindy, buen punto. He actualizado mi respuesta en consecuencia.
DW
2
@det ¿Por qué codicioso? ¿Qué significa "casi" resolver un problema de decisión?
Rafael
2
@Mehrdad: Por lo general, evalúa un algoritmo de aproximación por su error de peor caso: un límite superior de lo no óptimo que es. Entonces, por ejemplo, podría decir que un algoritmo de aproximación dado siempre encuentra un resultado que es al menos cinco sextos del resultado óptimo. No hay forma real de traducir eso a un problema de decisión; si su algoritmo veces emite (por ejemplo) 0.1, a continuación, ya sea a veces es de un 0,9 (en cuyo caso sería mejor, en el peor de los casos, siempre emiten 0,5), o la -ness "aproximada" es una farsa y "0,1 "en realidad solo significa" 0 ".
ruakh
14

La razón por la que no ve cosas como las proporciones de aproximación en los problemas de toma de decisiones es que generalmente no tienen sentido en el contexto de las preguntas que generalmente se hacen sobre los problemas de toma de decisiones. En una configuración de optimización, tiene sentido porque es útil estar "cerca". En muchos entornos, no tiene sentido. No tiene sentido ver con qué frecuencia está "cerca" en un problema de logaritmo discreto. No tiene sentido ver con qué frecuencia está "cerca" de encontrar un isómero gráfico. Del mismo modo, en la mayoría de los problemas de toma de decisiones, no tiene sentido estar "cerca" de la decisión correcta.

Ahora, en implementaciones prácticas, hay muchos casos en los que es útil saber qué parte de los problemas se puede decidir "rápidamente" y qué parte no. Sin embargo, a diferencia de la optimización, no hay una forma única para cuantificar esto. Puede hacerlo estadísticamente, como sugiere, pero solo si conoce la distribución estadística de sus entradas. La mayoría de las veces, las personas que están interesadas en problemas de decisión no tienen tanta suerte de tener tales distribuciones.

Como estudio de caso, considere el problema de detención. Se sabe que el problema de detención es indecidible. Es una pena, porque es un problema realmente útil para poder resolver si está haciendo un compilador. En la práctica, sin embargo, encontramos que la mayoría de los programas son realmente muy fáciles de analizar desde una perspectiva problemática. Los compiladores aprovechan esto para generar un código óptimo en estas circunstancias. Sin embargo, un compilador debe reconocer que existe la posibilidad de que un bloque de código en particular no sea decidible. Cualquier programa que se base en que el código sea "probablemente decidible" puede meterse en problemas.

Sin embargo, la métrica utilizada por los compiladores para determinar qué tan bien resuelven estos casos particulares del problema de detención es muy diferente de una métrica utilizada por un programa de criptografía para probar si un par particular de primos está aceptablemente endurecido contra los ataques. No hay una solución única para todos. Si desea una métrica de este tipo, querrá adaptarla para que se adapte a su espacio de problemas particulares y a su lógica empresarial.

Cort Ammon - Restablece a Monica
fuente
Entonces, según tengo entendido, ¿la única forma de resolver un problema de decisión es diseñar el algoritmo óptimo que puede ser muy ineficiente? Debido a que tengo un problema de decisión (NP-complete) y me pidieron que inventara un algoritmo codicioso (rápido) para encontrar una solución. ¿Como puedo resolver esto? ¿Conoces algún artículo que se centre en este tipo de problemas?
Ribz el
1
@det Empuje hacia atrás y restablezca el problema. Si tiene un problema de NP completo, está bastante atascado, pero es muy probable que en realidad no necesite resolver uno. Por ejemplo, no siempre necesitas la respuesta perfecta. Tal vez cerca es lo suficientemente bueno. O tal vez pueda resolver el problema para un subconjunto de casos que son fáciles y puntualizar los que son difíciles. Como ejemplo, los algoritmos de empaque son a menudo NP-completos, pero son comunes los algoritmos que obtienen de manera confiable dentro del 5% del óptimo utilizando enfoques probabalísticos.
Cort Ammon - Restablece a Mónica el
2
Honestamente, que me digan que invente un algoritmo codicioso para resolver un programa NP-complete es literalmente lo mismo que tener la tarea de enfrentar a toda la comunidad informática / matemática sin ayuda. Si encuentra un algoritmo para un programa de NP-completo en el tiempo P, en el muy menos que ganaría el premio arcilla $ 1 millón para la solución de P = NP. En realidad, los efectos de su descubrimiento darían nueva forma a la informática tal como la conocemos, y mejoraría por completo toda la industria de seguridad / criptografía de la noche a la mañana. Es mejor tener la redacción de la tarea ajustada para que no se pueda completar NP.
Cort Ammon - Restablece a Monica el
He usado un algoritmo exacto y codicioso para un problema de NP completo. Solo necesitaba resolver un caso pequeño, y podría obtener un servidor de 64 procesadores durante un fin de semana.
Patricia Shanahan
8

Además de las respuestas existentes, permítanme señalar que hay situaciones en las que tiene sentido tener una solución aproximada para un problema de decisión, pero funciona de manera diferente de lo que piensas.

Con estos algoritmos, solo uno de los dos resultados se determina con certeza, mientras que el otro podría ser incorrecto. Tome la prueba de Miller-Rabin para los números primos , por ejemplo: si la prueba determina que un número no es primo, ese resultado es seguro. Pero en el otro caso solo significa que el número es probablemente primo. Dependiendo de cuánto tiempo de cómputo esté dispuesto a invertir, puede aumentar su confianza en el resultado, pero no será del 100% como lo es para el caso no principal.

Esto es especialmente poderoso cuando se abordan problemas indecidibles: podría escribir una herramienta que intente resolver el problema de detención de un fragmento de código específico. Si puede encontrar una prueba de que el programa no se repetirá sin parar, puede reclamarlo con 100% de certeza. Si no puede encontrar una prueba de este tipo, es posible que el flujo de control del programa sea demasiado complicado para que su herramienta lo analice, pero no es una prueba de que se repetirá para siempre. Al simplificar las estructuras de control, es posible que pueda crear un programa equivalente que sea lo suficientemente simple como para que la herramienta demuestre que se detendrá con seguridad.

ComicSansMS
fuente
Hay una gran diferencia entre los algoritmos probabilísticos (su respuesta) y de aproximación (la pregunta). En particular, la combinación de ambos es una raza muy especial.
Raphael
Además, sabemos que no existen algoritmos probabilísticos para el problema de detención, suponiendo una interpretación razonable del término en este contexto.
Raphael
@Raphael No tenía la intención de que mi respuesta fuera específica de los algoritmos probabilísticos. De acuerdo, para Miller-Rabin ese es el caso, pero como mencionó usted mismo, esto ya no es cierto para el ejemplo del problema de detención, y supongo que tampoco será cierto para la mayoría de los casos en los que encuentra este comportamiento. El punto que quería transmitir es simplemente que solo obtendrá certeza sobre un resultado, pero no sobre el otro.
ComicSansMS
Si no está diciendo más que eso, algunos problemas son solo semi-computables, no creo que esté respondiendo la pregunta.
Raphael
@Raphael Mi respuesta tampoco es específica para problemas semi-computables. De hecho, no creo que el enfoque que describí se aplique incluso a problemas semi-computables. Allí estará seguro si aterrizó en la rama indefinida de la función, por lo que puede afirmar con certeza que no hay resultado. Lo que describí se reduce a: puede haber una respuesta, pero el algoritmo puede no haber sido lo suficientemente difícil como para tropezar con él.
ComicSansMS