Problemas de otimização "NP-complete"

24

Estou um pouco confuso com alguma terminologia que encontrei em relação à complexidade dos problemas de otimização. Em uma classe de algoritmos, tive o grande problema de parcimônia descrito como NP-complete. No entanto, não sei exatamente o que o termo NP-completo significa no contexto de um problema de otimização. Isso significa apenas que o problema de decisão correspondente é NP-completo? E isso significa que o problema de otimização pode de fato ser mais difícil (talvez fora do NP)?

Em particular, estou preocupado com o fato de que, embora um problema de decisão completo de NP seja verificável em tempo polinomial, uma solução para um problema de otimização correspondente não parece ser verificável em tempo polinomial. Isso significa que o problema não está realmente em NP ou a verificação do tempo polinomial é apenas uma característica dos problemas de decisão de NP?

Aniket Schneider
fonte
3
verifique esta questão
Ran G.
1
Também esta pergunta: Versão de otimização de problemas de decisão .
Kaveh
1
@RanG., Não tenho certeza se esta é uma duplicata exata .
Kaveh
@ Kaveh, você está certo, mas a grande resposta de uli responde totalmente a essa pergunta.
Ran G.
@RanG., Pode haver mais de uma ótima resposta. :)
Kaveh

Respostas:

13

Uma tentativa de resposta parcial:

Os problemas de decisão já foram investigados por algum tempo antes que os problemas de otimização aparecessem, no sentido em que são tratados da perspectiva dos algoritmos de aproximação.

Você deve ter cuidado ao transmitir os conceitos dos problemas de decisão. Isso pode ser feito e pode ser fornecida uma noção precisa da integridade do NP para problemas de otimização. Veja esta resposta . É claro que é diferente da completude do NP para problemas de decisão, mas é baseado nas mesmas idéias (reduções).

Se você se deparar com um problema de otimização que não permita uma verificação com uma solução viável, não há muito o que fazer. É por isso que geralmente se assume que:

  • Podemos verificar com eficiência se a entrada é realmente uma instância válida do nosso problema de otimização.
  • O tamanho das soluções viáveis ​​é limitado polinomialmente pelo tamanho das entradas.
  • Podemos verificar com eficiência se uma solução é uma solução viável da entrada.
  • O valor de uma solução pode ser determinado com eficiência.

Caso contrário, não há muito que possamos esperar alcançar.

A classe de complexidade NP contém apenas problemas de decisão por definição. Portanto, não há problemas de otimização. E a definição baseada em Verificador de NP você menciona é específico para NP . Não o encontrei com problemas de otimização.

Se você quiser verificar se uma solução não é apenas viável, mas também ideal, eu diria que isso é tão difícil quanto solucionar o problema de otimização original porque, para refutar uma solução viável e possivelmente ótima como não ideal, você precisa fornecer uma solução melhor, o que pode exigir que você encontre a verdadeira solução ideal.

Mas isso não significa que o problema de otimização seja mais difícil. Veja esta resposta , que depende, é claro, das definições precisas.

uli
fonte
Você pode fornecer um artigo ou uma referência de livro, onde posso encontrar mais informações sobre uma definição precisa, redução, etc., da dureza NP para problemas de otimização? Até agora, eu não conseguia descobrir um. Isso seria muito interessante para mim. Obrigado.
John Threepwood
-1

A razão pela qual a maioria dos problemas de otimização pode ser classificada como P, NP, NP-completa etc. são as condições de Kuhn-Tucker. Vou falar em termos de problemas de programação linear, mas o KTC se aplica a muitos outros problemas de otimização. Para cada problema de otimização, há um duplo. Se o objetivo no problema original é maximizar alguma função, a dupla (geralmente) tem uma função a ser minimizada. * Soluções viáveis, mas não ideais para o problema original serão inviáveis ​​/ inválidas para o problema duplo e vice-versa. -versa. Se, e somente se, uma solução for viável para o primário e o duplo, é uma solução ideal para ambos. (Tecnicamente, pode ser uma das muitas soluções ideais que oferecem o mesmo resultado.)

Portanto, encontrar uma solução ideal para um problema de otimização é equivalente a encontrar uma solução válida para o primário e o dual. Você pode usar algoritmos de otimização para encontrar essa solução, mas o processo geral é uma prova de existência.

  • Se você deseja alternar entre minimização e maximização, multiplique a função objetivo por -1.
Robert I. Eachus
fonte
3
Não vejo como as condições da KKT se relacionam com a dureza NP, você poderia elaborar isso?
Lagarto discreto
2
Realmente não vejo como isso responde à pergunta. P , NP , etc., são classes de problemas de decisão. Problemas de otimização não são problemas de decisão; portanto, eles não estão em nenhuma dessas classes por definição .
precisa saber é o seguinte
2
Também não vejo como isso responde à pergunta - esse é um comentário interessante, mas parece responder a uma pergunta diferente da que foi feita. A pergunta pergunta o que significa dizer que um problema de otimização é NP completo e se é possível dizer que problemas de otimização estão no NP, já que eles não são um problema de decisão. Isso descreve como, dado um problema de otimização (onde as soluções não são verificáveis), geralmente podemos construir um problema correspondente no qual as soluções podem ser verificadas. Coisas muito interessantes, mas não tenho certeza de que responda à pergunta que foi feita.
DW
1
@DW A principal razão pela qual acho que isso realmente não está respondendo à pergunta é que, além do que já foi mencionado, a KKT limita a configuração à otimização matemática de funções 'regulares' (por exemplo, contínuas, diferenciáveis, convexas). Essa configuração não é aplicável à maioria dos problemas difíceis de NP.
Lagarto discreto