Todos os problemas de programação linear inteira são NP-Hard?

11

Pelo que entendi, o problema de atribuição está em P, pois o algoritmo húngaro pode resolvê-lo em tempo polinomial - O (n 3 ). Também entendo que o problema de atribuição é um problema de programação linear inteira , mas a página da Wikipedia afirma que esse é NP-Hard. Para mim, isso implica que o problema de atribuição está no NP-Hard.

Mas certamente o problema de atribuição não pode estar em P e NP-Hard, caso contrário, P seria igual a NP? A página da Wikipedia significa simplesmente que o algoritmo geral para resolver todos os problemas de ILP é NP-Hard? Algumas outras fontes afirmam que o ILP é NP-Hard, então isso realmente está confundindo minha compreensão das classes de complexidade em geral.

Matt
fonte
4
NP-hard significa que (a menos que P = NP) todo algoritmo determinístico de politempo falhe em algum conjunto (infinito) de instâncias. Geralmente, também existem conjuntos de instâncias fáceis.
Sasho Nikolov
11
Observe que a declaração não é "todo IP é difícil de NP", mas "resolver todo IP é difícil de NP".
Raphael
11
Como uma observação, IP para a dimensão fixa está em P.
A.Schulz

Respostas:

20

Se um problema for NP-Hard, significa que existe uma classe de instâncias desse problema que são NP-Hard. É perfeitamente possível que outras classes específicas de instâncias sejam solucionáveis ​​em tempo polinomial.

Considere, por exemplo, o problema de encontrar uma coloração tridimensional de um gráfico . É um problema conhecido do NP-Hard. Agora imagine que suas instâncias estão restritas a gráficos que são, por exemplo, árvores. Claramente, você pode encontrar facilmente uma cor 3 de uma árvore em tempo polinomial (na verdade, você também pode encontrar uma cor 2).

Considere problemas de decisão por um segundo. Um método para provar a dureza de um problema de decisão é conceber uma redução polinomial (Karp) de outro problema Q que é conhecido por NP-Hard. Nesta redução, você mostra que existe uma função f que mapeia cada instância q do problema Q para uma instância do problema P, de modo que: q é uma instância yes para QPQfqQPq é um exemplo sim por P . Isso implica que a solução de f ( q ) deve ser "pelo menos tão difícil" quanto a solução de q .Qf(q)Pf(q)q

Observe como ele não é necessário para a imagem de ser igual ao conjunto das instâncias de P . Portanto, é perfeitamente possível que o problema P restrito a algum subconjunto de instâncias não seja difícil.fPP

Para retornar à sua pergunta original:

  • O problema de atribuição pode ser resolvido em tempo polinomial, ou seja, uma solução para cada instância do problema de atribuição pode ser calculada em tempo polinomial.
  • ILP é NP-Hard: em geral, pode ser difícil calcular uma solução para um problema de ILP, ou seja, há casos de ILP que são difíceis.
  • Algumas instâncias específicas de ILP podem ser resolvidas em tempo polinomial.
Steven
fonte
fQQfQ
fQQP
14

Não, casos especiais podem ser mais fáceis.

ai0i[1..n]

mini=1nxiai

st e para .i=1nxi1xiNi[1 ..n]
 xiNi[1..n]

Ele encontra o mínimo entre (aquele para o qual, inevitavelmente, em uma solução ideal). Encontrar o mínimo de números é claramente um problema polinomial.a1,,anxi=1n

Rafael
fonte
0

Você pode modelar um problema polinomialmente solucionável como um IP. Isso não significa que o problema seja difícil para o NP. Simplesmente significa que não existe um algoritmo polinomial conhecido para resolver o modelo IP do seu problema (a menos que P = NP).

Então, como você sugeriu, o problema de atribuição está em P, mas seu modelo de IP é NP-difícil.

Austen
fonte
3
O IP na resposta de Raphael pode ser resolvido em tempo polinomial. Em outras palavras, em geral, não conhecemos um algoritmo rápido para resolver IPs, mas há casos especiais de problemas de IP para os quais temos algoritmos rápidos.
Juho 22/07
0

Não, existe um tipo especial de programa inteiro; se a matriz de restrição é TUM (matriz totalmente unimodular), ela pode ser relaxada no programa linear, que pode ser resolvido em tempo polinomial.

Jianhao Ma
fonte
-4

O problema de atribuição não é um ILP, mas um problema de LP e, portanto, não é difícil para NP.

Julia
fonte
4
Não sei por que você acha que o problema da atribuição não é um ILP. Acontece que, nesse caso, a solução ideal para o programa linear também é a solução ideal para o programa linear inteiro ... mas isso não significa que não seja uma instância do ILP.
DW
Além disso, as instâncias individuais por si mesmas nunca são difíceis para o NP. Você quer dizer "esta é realmente uma instância fácil", mas essa é uma afirmação muito mais complicada (defina "fácil").
Raphael