¿Existen ejemplos naturales conocidos de problemas de optimización para los cuales es mucho más fácil producir una solución óptima que evaluar la calidad de una solución candidata dada?
En aras de la concreción, podemos considerar problemas de optimización solucionables en tiempo polinómico de la forma: "dado x, minimizar ", donde f : { 0 , 1 } ∗ × { 0 , 1 } ∗ → N es, digamos, # P-hard. Tales problemas existen claramente (por ejemplo, podríamos tener f ( x , 0 ) = 0 para todas las x incluso si f es indiscutible), pero estoy buscando problemas `` naturales '' que exhiban este fenómeno.
Aquí hay un ejemplo, donde uno puede producir una solución en tiempo polinómico, pero evaluar una solución dada es NP- duro.
Nota: Si solo queremos verificar si la solución es óptima , entonces es fácil, porque se sabe que el gráfico de Turan es el óptimo único, por lo que es suficiente comparar el gráfico candidato con el gráfico de Turan, que tiene una estructura simple . Por otro lado, si queremos evaluar la calidad de una solución candidata, como se solicitó en la pregunta, es decir, si es factible y qué tan lejos está de lo óptimo, entonces tenemos que verificar si satisface la máxima camarilla restricción.
fuente