Existem exemplos naturais conhecidos de problemas de otimização para os quais é muito mais fácil produzir uma solução ideal do que avaliar a qualidade de uma determinada solução candidata?
Por questões de concretude, podemos considerar problemas de otimização solucionáveis em tempo polinomial da forma: "dado x, minimize ", onde f : { 0 , 1 } ∗ × { 0 , 1 } ∗ → N é, digamos, # P-difícil. Tais problemas existem claramente (por exemplo, poderíamos ter f ( x , 0 ) = 0 para todos x, mesmo que f seja incontestável), mas estou procurando problemas `` naturais '' que exibam esse fenômeno.
Aqui está um exemplo, onde é possível produzir uma solução em tempo polinomial, mas avaliar uma determinada solução é NP -hard.
Nota: Se queremos apenas verificar se a solução é ótima , é fácil, porque o gráfico de Turan é conhecido como o ideal único, portanto basta comparar o gráfico candidato com o gráfico de Turan, que possui uma estrutura simples. . Por outro lado, se queremos avaliar a qualidade de uma solução candidata, conforme solicitado na pergunta, ou seja, se é viável e a que distância está do ideal, temos que verificar se ela satisfaz a camarilha máxima restrição.
fonte