Fácil de otimizar, mas difícil de avaliar

10

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.f(x,y)f:{0,1}×{0,1}Nf(x,0)=0xf

david
fonte

Respostas:

3

No artigo [1], existe um problema com a propriedade de que encontrar um elemento ideal leva tempo polinomial, apesar de calcular os valores da função objetivo ser NP-difícil (significa que avaliar a qualidade de uma determinada solução candidata também é NP-difícil). )

[1] TCECheng, Y.Shafransky, CTNg. Uma abordagem alternativa para provar a dureza NP dos problemas de otimização. European Journal of Operational Research 248 (2016) 52–58.

Yakov Shafransky

Yakov Shafransky
fonte
Compartilhar alguns detalhes aqui seria bom. :)
Michael Wehar
15

Aqui está um exemplo, onde é possível produzir uma solução em tempo polinomial, mas avaliar uma determinada solução é NP -hard.

n,kkn

nk

T(n,k)k

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.

Andras Farago
fonte