Comment prouver qu'un problème n'est PAS NP-Complete?

17

Existe-t-il une technique générale pour prouver qu'un problème n'est PAS NP-Complete?

J'ai reçu cette question à l'examen qui m'a demandé de montrer si un problème (voir ci-dessous) est NP-Complete. Je ne pouvais pas penser à une vraie solution, et je viens de prouver que c'était en P. Évidemment, ce n'est pas une vraie réponse.

NP-Complete est défini comme l'ensemble des problèmes qui se trouvent dans NP, et tous les problèmes NP peuvent y être réduits. Toute preuve doit donc contredire au moins l'une de ces deux conditions. Ce problème spécifique, est en effet en P (et donc en NP). Je suis donc obligé de prouver qu'il y a un problème dans NP qui ne peut pas être réduit à ce problème. Comment diable cela peut-il être prouvé ??

Voici le problème spécifique que l'on m'a donné à l'examen:

Soit l'ensemble des chaînes sous forme normale disjonctive . Soit le langage des chaînes de qui peuvent être satisfaites par une affectation de variables. si est en NP-Complete.DNFDNFSATDNFDNFSAT

Sans titre
la source
8
S'il était prouvé que DNF-SAT n'était pas NP-complet, cela impliquerait immédiatement que , comme vous l'avez montré. Ainsi, je crois que la réponse qu'ils cherchaient est exactement ce que vous avez donnée (et vous étiez probablement supposé implicitement supposer que P N P ). Pourtant, c'est une question très trompeuse. PNPPNP
Shaull
Vous avez raison, je comprends donc que ce problème est équivalent au problème de et qu'une solution à l'un résout également l'autre. P=NP
Untitled
Pourquoi dites-vous de prouver que DNFSAT est en P que "évidemment ce n'est pas une vraie réponse"?
András Salamon
5
@ AndrásSalamon Il suppose que , qui est une déclaration non prouvée. PNP
Untitled
1
@Untitled: il ne suppose pas en fait P ≠ NP, voir ma réponse.
András Salamon

Réponses:

8

Sur la base des commentaires, vous semblez vouloir une réponse inconditionnelle.

Cependant, DNF-SAT est en L, en affectant des variables pour satisfaire la première disjonction. Par conséquent, s'il est NP-complet, alors L = NP.

D'un autre côté, si L = NP alors DNF-SAT est NP-complet sous les réductions de l'espace de log, trivialement. (En fait, si L = NP, alors chaque problème dans NP est NP-complet sous les réductions de l'espace de log.)

Il s'ensuit que L = NP ssi DNF-SAT est NP-complet sous les réductions de l'espace de log.

Donc, vous ne pouvez pas actuellement déclarer sans condition que DNF-SAT n'est pas NP-complet, comme vous semblez vouloir le faire. Il n'est pas nécessaire de supposer P ≠ NP, mais la réponse doit être conditionnée à quelque chose, et L ≠ NP est l'hypothèse la plus faible possible qui garantit le résultat souhaité.

András Salamon
la source
Intéressant. Donc , ce problème est équivalent au problème de . Pourriez-vous expliquer pourquoi vous dites que L N P est une hypothèse faible? L=NP=P=NPCLNP
Untitled
3
Si alors ψ est plus faible que ϕ . ϕψψϕ
András Salamon
14

Un problème est NP-complet si elle est à la fois NP- dur et dans NP. Cela signifie que vous devez réfuter l'un de ces deux éléments.Q

  1. En supposant que P NP, vous pouvez donner un algorithme polynomial résolution Q . Plus rarement, en supposant que l'isomorphisme du graphe n'est pas NP-difficile, vous pouvez montrer que Q est polytemporaire réductible à l'isomorphisme du graphe.QQ
  2. Vous montrez que n'est pas dans NP. C'est plus difficile, et vous devez généralement utiliser d'autres hypothèses, comme le non effondrement de la hiérarchie polynomiale, que NP coNP ou montrer qu'il est difficile pour une autre classe supérieure à NP, par exemple en montrant qu'il est dur NEXPTIME.Q

Habituellement, la réponse est de donner un algorithme de temps polynomial, qui serait le plus simple pour DNF-SAT, mais cela repose sur l'hypothèse que P NP. Cependant, prouver que DNF-SAT n'est pas NP-complet sans aucune hypothèse implique, comme le souligne Shaull, de prouver que P NP, ce qui est quelque peu plus délicat.

Pål GD
la source
1
Les deux techniques que vous avez fournies reposent sur une sorte d'hypothèse non prouvée. Pensez-vous qu'il pourrait y avoir un moyen concret (pas d'hypothèses) de résoudre un problème de ce genre?
Untitled
Oh, et je ne parlais pas de ce problème spécifique, car comme l'a déclaré Shaull, ce problème est toujours ouvert. Je voulais dire prouver la CoNP-Complétude en général.
Untitled
2
@Untitled Vous ne pensiez probablement pas à l'exhaustivité du coNP. Une façon de le montrer est par mon point (2), prouvant que le problème est NEXPTIME-difficile. Nous savons que NP NEXPTIME, donc cela le prouverait. Prouver qu'un problème Q est NEXPTIME-dur, signifierait donc que Q ne peut pas être dans NP et ne peut donc pas être NP-complet. QQ
Pål GD
10

Par la hiérarchie temporelle non déterministe, vous pouvez montrer que le problème est -hard; comme N PN E X P , il est impossible de réduire le problème en temps polynomial à tout problème en N P , de sorte que le problème ne sera pas en N P .NEXPNPNEXPNPNP

Cependant, si votre problème n'est pas aussi difficile, vous aurez peut-être du mal à prouver qu'il n'est pas dans ; et si elle est en N P , vous serez aux abois pour montrer que N P n'est pas Karp réductible à votre problème sans supposer que PN P .NP NPNPPNP

Niel de Beaudrap
la source
0

Comme c'est le cas pour toutes les preuves, il n'y a pas de formule pour prouver une déclaration, vous devez faire des suppositions intelligentes, des essais et des erreurs et j'espère que vous serez en mesure de prouver ce que vous essayez de prouver. Pour prouver qu'un problème n'est PAS NP-complet, réfutez la définition (loi de DeMorgran), c'est-à-dire prouver le problème PAS en NP ou prouver le problème PAS NP-difficile.

saadtaame
la source
0

Je crois que ce que le conférencier veut vraiment, c'est que vous puissiez distinguer les problèmes qui sont en P des problèmes qui sont NP-complets dans le sens donné. Pouvez-vous construire un algorithme efficace? si oui, il est suspecté de ne pas être NP-complet car nous ne pensons pas que les langues en P soient NP-complètes! sinon vous devez encore prouver que le problème est NP-difficile!

notons qu'il existe des problèmes dont nous ne connaissons pas le statut tels que l'isomorphisme du graphe, la factorisation d'un nombre donné, ... nous pensons que ces problèmes ne sont pas NP-complets mais personne ne pourrait le prouver! en particulier, nous avons des preuves que l'isomorphisme du graphe n'est pas complet en NP! l'autre problème est la conjoncture de jeu unique que nous soupçonnons que le jeu unique est NP-complet mais aucune preuve n'existe! donc l'approche que vous décrivez n'est pas utile!

fayez abd-alrzaq deab
la source