El término 'problema de optimización de NP-duro' parece demasiado amplio para permitir encontrar una respuesta satisfactoria.
Por ejemplo, no veo qué impide que los problemas de decisión se consideren problemas de optimización NP-hard si se considera, por ejemplo, el problema MAX-CNF-SAT con las soluciones calificadas como piso (k/N) , donde k es el número de cláusulas satisfechas y N es el número total de cláusulas en la instancia (que es claramente computable en tiempo polinomial), entonces cualquier valoración que arroje un 1 en esta fórmula deberá satisfacer la fórmula completa. Asumamos que estamos maximizando el piso (k/N) y le llamamos el problema de optimización FLOOR-CNF-SAT :)
Esto implica que puede reducir la TAUTOLOGÍA a dicho problema de optimización - niegue la entrada y agregue cualquier solución como S . Incluso puede agregar una variable ficticia para asegurarse de que la solución inicial obtiene un 0 en el problema FLOOR-CNF-SAT. La negación es polinomial en el tiempo.
Entonces, si un solucionador para el problema propuesto S no es óptimo, debe haber una valoración que rinde un 1 de acuerdo con nuestra función y satisface la fórmula completa, proporcionando a su vez una valoración que no satisface la entrada original a TAUTOLOGY.
Haciendo trampa ligeramente (utilizando un problema de optimización creado artificialmente) hemos establecido el problema 'es óptimo' como co-NP-complete, ya que TAUTOLOGY se muestra fácilmente como co-NP-completo.
Según su propio argumento, el problema de decisión "es óptimo" es co-NP-hard, ya que como testigo solo necesita una solución mejor: puntuar S, calificar al testigo y comparar.
Realmente no me siento muy bien con esta reducción, pero no puedo mejorar fácilmente la clase de problema. Si necesita que haya instancias que puntúen arbitrariamente alto y no solo {0, 1}, podría usar N * piso (k/N).Una mejora de la clase podría ser considerar solo un problema como un problema de optimización NP-hard si para cada K existe una instancia que tiene al menos K soluciones que puntúan de manera diferente.
Creo que todavía puedo engañar a mi manera a través de que:
Considérese una reducción de las variables que añade N ficticias a la entrada de la tautología de la siguiente manera:
d1 && d2 && d3 ... && dN && (S)
donde S es la entrada negada. Como una valoración inicial elijo d1, ..., dN = falso, pero como puntaje otorgo una función que devuelve 2N - 1 si las primeras N cláusulas son todas falsas, de lo contrario devuelve el número de cláusulas satisfechas. Dicha función solo devolvería 2N si se cumplieran todas las cláusulas, pero podría tener fácilmente al menos N valores distintos.
Me temo que sin algunas condiciones de regularidad complicadas en la función de puntuación esto es lo mejor que podemos obtener, a menos que considere la definición de un problema de optimización NP-difícil como un problema para el cual, dada una solución candidata , podemos verificar en tiempo polinomial si S es óptimo ', en cuyo caso' es-óptimo 'es claramente P y no es nada divertido:/
Suponiendo que la variante de decisión del problema de optimización es NP-completa, ha esbozado una prueba de que la verificación de las soluciones óptimas está en la red coNP. La ruta más directa hacia un resultado de dureza sería una reducción polinómica en el tiempo de muchos a partir de un problema duro de coNP, pero tal reducción tendría dificultades para encontrar una solución para verificar. Tomé un curso de complejidad de nivel de posgrado y pienso que esto es apropiado para cstheory. – userOVER9000
Si la Optimización era un problema de minimización de enteros positivos (es decir, la respuesta siempre es un entero positivo), podría hacer una búsqueda binaria usando el verificador "IsOptimal", y así parece que también sería NP-Hard ... –
@Moron: ¿Es esto necesariamente el caso? Tenga en cuenta que el problema requiere una solución candidata real, no simplemente su "valor". – mhum