Chaque problème de NP a-t-il une formulation ILP poly-dimensionnée?

14

Étant donné que la programmation linéaire entière est NP-complète, il y a une réduction de Karp de tout problème dans NP. Je pensais que cela impliquait qu'il existe toujours une formulation ILP de taille polynomiale pour tout problème de NP.

Mais j'ai vu des articles sur des problèmes spécifiques de NP où les gens écrivent des choses comme "c'est la première formulation poly-dimensionnée" ou "il n'y a pas de formulation poly-dimensionnée connue". Voilà pourquoi je suis perplexe.

complexity-theory np-complete reductions linear-programming Andy
la source
8
Vous devez indiquer un exemple ou donner un devis plus complet;)
hugomg
1
Il existe une réduction polynomiale de chaque problème NP-complet à tout autre problème NP-complet. Cependant, ce n'est pas parce que nous savons qu'il existe que nous savons comment le construire.
Joe
3
@Joe bien, nous savons comment réduire tout problème en NP à 3 sat, et chaque preuve de problème NP-complète pratique provient d'une chaîne de réductions de 3 sat, de sorte que vous pouvez toujours composer des réductions à partir de n'importe quel problème NPC donné vers tout autre.
andy
10
@andy ne viens-tu pas de répondre à ta question avec ce commentaire? Vous savez que chaque instance de problème NP peut être écrite comme une instance 3-SAT polysized, et vous savez qu'une instance 3-SAT peut être écrite comme une instance ILP polysized, et le polynôme appliqué au polynomial est un autre polynôme ... que faire de plus attendre d'une réponse?
Artem Kaznatcheev
2
Quand quelqu'un dit que c'est la première formulation poly-taille, ce qu'ils veulent dire c'est que c'est la première formulation explicitement donnée . Les réductions obtenues via SAT (même si l'on prend soin de tous les détails) ne sont pas belles et difficiles à travailler. Nous voulons généralement des formulations naturelles et faciles à travailler.
Kaveh

Réponses:

5

Cette réponse est principalement un récapitulatif des commentaires sur la question ci-dessus.

Si un problème est NP-complet, il peut en effet être réduit à ILP, en utilisant les réductions de Karp (- Joe, andy). Les allégations de «formulations de taille polynomiale» d'un problème à un autre sont probablement conçues comme des formulations plus directes, par opposition à de multiples réductions par le biais de SAT (- Kaveh).

Realz Slaw
la source
1

Oui. Chaque problème de NP a une formulation ILP de taille polynomiale.

Voici pourquoi. Chaque problème NP a une formulation de taille polynomiale comme instance de SAT. De plus, tous les opérateurs booléens habituels - OU logique, ET logique, NON logique, etc. - peuvent être exprimés en ILP, en utilisant un nombre constant de variables et d'inégalités par opérateur booléen. Voir Opérations logiques booléennes expresses en programmation linéaire (ILP) zéro-un pour plus de détails sur la façon de procéder. Ainsi, nous obtenons tout au plus une explosion de taille constante lors du passage de SAT à ILP. Cela implique qu'il existe une formulation de taille polynomiale de chaque problème NP en tant que problème ILP.

DW
la source