Todo problema de PN tem uma formulação de ILP de tamanho poli?

14

Como a Programação Linear Inteira é NP-completa, há uma redução de Karp de qualquer problema no NP. Eu pensei que isso implicava que sempre existe uma formulação de ILP de tamanho polinomial para qualquer problema no NP.

Mas já vi artigos sobre problemas específicos de PN, nas quais as pessoas escrevem coisas como "esta é a primeira formulação de tamanho pequeno" ou "não existe uma formulação conhecida de tamanho pequeno". É por isso que estou confusa.

complexity-theory np-complete reductions linear-programming andy
fonte
8
Deve-se apontar um exemplo ou dar uma citação mais completa;)
hugomg
1
Existe uma redução polinomial de todos os problemas de NP-completo para todos os outros problemas de NP-completo. No entanto, apenas porque sabemos que um existe, não significa que sabemos como construí-lo.
1616 Joe
3
Bem, sabemos como reduzir qualquer problema no NP para 3-sat, e todas as provas práticas de NP-completas vêm de uma cadeia de reduções do 3-sat, para que você sempre possa compor reduções de qualquer problema NPC para qualquer outro.
andy
10
@andy, você não respondeu sua pergunta com esse comentário? Você sabe que toda instância de problema NP pode ser gravada como uma instância 3-SAT polisizada, e você sabe que uma instância 3-SAT pode ser gravada como uma instância ILP polisizada, e o polinômio aplicado ao polinômio é outro polinômio ... o que mais você faz esperar de uma resposta?
Artem Kaznatcheev
2
Quando alguém diz que esta é a primeira formulação de tamanho único, o que eles querem dizer é que é a primeira dada explicitamente . As reduções obtidas através do SAT (mesmo que se cuide de todos os detalhes) não parecem boas e são difíceis de trabalhar. Geralmente, queremos formulações naturais e fáceis de trabalhar.
Kaveh

Respostas:

5

Esta resposta é principalmente uma recapitulação dos comentários sobre a pergunta acima.

Se um problema é NP-completo, pode realmente ser reduzido a ILP, usando as reduções de Karp (- Joe, andy). Reivindicações de "formulações de tamanho polinomial" de um problema para outro provavelmente significam formulações mais diretas, em oposição a múltiplas reduções através do SAT (- Kaveh).

Realz Slaw
fonte
1

Sim. Todo problema de NP tem uma formulação de ILP de tamanho polinomial.

Aqui está o porquê. Todo problema de NP tem uma formulação de tamanho polinomial como uma instância do SAT. Além disso, todos os operadores booleanos usuais - OR lógico, AND lógico, NOT lógico etc. - podem ser expressos em ILP, usando um número constante de variáveis ​​e desigualdades por operador booleano. Consulte Operações lógicas booleanas expressas na programação linear inteira zero (um) (ILP) para obter detalhes de como fazer isso. Assim, obtemos no máximo uma explosão de tamanho constante ao passar do SAT para o ILP. Isso implica que existe uma formulação em tamanho polinomial de cada problema de NP como um problema de ILP.

DW
fonte