Wie beweise ich, dass ein Problem NICHT NP-vollständig ist?

17

Gibt es eine allgemeine Methode, um zu beweisen, dass ein Problem NICHT NP-vollständig ist?

Ich habe diese Frage in der Prüfung erhalten, in der ich gefragt wurde, ob ein Problem (siehe unten) NP-Complete ist. Ich konnte mir keine wirkliche Lösung vorstellen und habe nur bewiesen, dass es in P. war. Offensichtlich ist dies keine wirkliche Antwort.

NP-Complete ist definiert als die Menge der Probleme, die sich in NP befinden, und alle NP-Probleme können darauf reduziert werden. Jeder Beweis sollte also mindestens einer dieser beiden Bedingungen widersprechen. Dieses spezifische Problem ist in der Tat in P (und damit in NP). Daher muss ich nur beweisen, dass es in NP ein Problem gibt, das sich nicht auf dieses Problem reduzieren lässt. Wie um alles in der Welt kann das bewiesen werden?

Hier ist das spezifische Problem, das mir bei der Prüfung gegeben wurde:

Sei die Menge von Zeichenketten in disjunktiver Normalform . Sei die Sprache von Strings aus , die durch eine gewisse Zuweisung von Variablen werden können. Zeigen Sie an, ob sich in NP-Complete befindet.D N F S A T D N F D N F S A TDNFDNFSATDNFDNFSAT

Ohne Titel
quelle
8
Wenn DNF-SAT werden kann bewiesen nicht als NP-vollständig, würde es sofort bedeuten , dass , wie Sie gezeigt haben. Daher glaube ich, dass die Antwort, nach der sie gesucht haben, genau das ist, was Sie gegeben haben (und Sie sollten wahrscheinlich implizit davon ausgehen, dass ). Dies ist jedoch eine sehr irreführende Frage. P N PPNPPNP
Shaull
Sie haben Recht, also verstehe ich, dass dieses Problem dem Problem von und eine Lösung für das eine auch das andere löst. P=NP
Ohne Titel
Warum beweisen Sie, dass DNFSAT in P enthalten ist, dass "dies offensichtlich keine echte Antwort ist"?
András Salamon
5
@ AndrásSalamon Es wird davon ausgegangen, dass PNP , was eine unbewiesene Aussage ist.
Ohne Titel
1
@Untitled: es geht eigentlich nicht von P ≠ NP aus, siehe meine Antwort.
András Salamon

Antworten:

8

Aufgrund der Kommentare möchten Sie anscheinend eine bedingungslose Antwort.

DNF-SAT befindet sich jedoch in L, indem Variablen zugewiesen werden, um die erste Disjunktion zu erfüllen. Wenn es also NP-vollständig ist, dann ist L = NP.

Wenn andererseits L = NP ist, dann ist DNF-SAT unter logarithmischen Raumverringerungen trivial NP-vollständig. (Wenn L = NP, dann ist in der Tat jedes Problem in NP NP-vollständig unter logspace Reductions.)

Daraus folgt, dass L = NP ist, wenn DNF-SAT unter Reduzierung des logarithmischen Bereichs NP-vollständig ist.

Daher können Sie derzeit keine bedingungslose Aussage darüber treffen, dass DNF-SAT nicht NP-vollständig ist, wie Sie es zu wollen scheinen. Es ist nicht notwendig, P ≠ NP anzunehmen, aber die Antwort muss von etwas abhängig sein, und L ≠ NP ist die schwächste mögliche Hypothese, die das gewünschte Ergebnis garantiert.

András Salamon
quelle
Interessant. So ist dieses Problem für das Problem der äquivalente . Können Sie erklären, warum Sie sagen, L N P sei eine schwache Annahme? L=NP=P=NPCLNP
Ohne Titel
3
Wenn ist ψ schwächer als ϕ . ϕψψϕ
András Salamon
14

Ein Problem ist NP-vollständig, wenn es sowohl NP- hart als auch in NP ist. Dies bedeutet, dass Sie einen dieser beiden Punkte widerlegen müssen.Q

  1. Unter der Annahme, dass P NP, können Sie einen polynomialen Zeitalgorithmus angeben, der Q löst . Seltener kann unter der Annahme, dass der Graphisomorphismus nicht NP-hart ist, gezeigt werden, dass Q polyzeitreduzierbar für den Graphisomorphismus ist.QQ
  2. Sie zeigen, dass nicht in NP ist. Dies ist schwieriger, und Sie müssen in der Regel andere Annahmen wie das Nichtzusammenbrechen der Polynomhierarchie verwenden, z. B. NP coNP, oder zeigen, dass es für eine andere Klasse, die höher als NP ist, schwierig ist, z.Q

Normalerweise lautet die Antwort, einen polynomiellen Zeitalgorithmus anzugeben, der für DNF-SAT am einfachsten wäre, aber dies beruht auf der Hypothese, dass P NP. Allerdings beweist , dass DNF-SAT nicht NP-vollständig ist , ohne irgendwelche Annahmen impliziert, wie Shaull weist darauf hin, was beweist , dass P NP, so dass etwas schwieriger ist.

Pål GD
quelle
1
Beide Techniken, die Sie zur Verfügung gestellt haben, beruhen auf einer Art unbewiesener Annahme. Denken Sie, es könnte einen konkreten Weg (keine Annahmen) geben, um ein Problem dieser Art zu lösen?
Ohne Titel
Oh, und ich meinte dieses spezielle Problem nicht, denn wie Shaull feststellte, ist dieses Problem immer noch offen. Ich wollte die CoNP-Vollständigkeit im Allgemeinen nachweisen.
Ohne Titel
2
@Untitled Du hast wahrscheinlich nicht die Vollständigkeit von CoNP gemeint. Ein Weg, dies zu zeigen, ist durch meinen Punkt (2) zu beweisen, dass das Problem NEXPTIME-schwer ist. Wir wissen, dass NP NEXPTIME ist, das würde es also beweisen. Der Nachweis, dass ein Problem Q NEXPTIME-schwer ist, würde daher bedeuten, dass Q nicht in NP und somit nicht NP-vollständig sein kann. QQ
Pål GD
10

Anhand der nicht deterministischen Zeithierarchie können Sie zeigen, dass das Problem -hard ist; als N PN E X P ist es unmöglich, das Problem in der Polynomzeit auf irgendein Problem in N P zu reduzieren , so dass das Problem nicht in N P sein wird .NEXPNPNEXPNPNP

Wenn Ihr Problem jedoch nicht annähernd so schwierig ist, kann es schwierig sein, zu beweisen, dass es nicht in . und wenn es in N P ist , werden Sie schwerlich zeigen, dass N P für Ihr Problem nicht Karp-reduzierbar ist, ohne anzunehmen, dass PN P ist .NP NPNPPNP

Niel de Beaudrap
quelle
0

Wie bei allen Beweisen gibt es keine Formel, um eine Aussage zu beweisen. Sie müssen intelligent raten, probieren und hoffentlich können Sie beweisen, was Sie zu beweisen versuchen. Um zu beweisen, dass ein Problem NICHT NP-vollständig ist, negieren Sie die Definition (DeMorgran-Gesetz), dh beweisen Sie das Problem NICHT in NP oder beweisen Sie das Problem NICHT NP-schwer.

Saadtaame
quelle
0

Ich glaube, der Dozent möchte wirklich, dass Sie Probleme in P von Problemen unterscheiden können, die in der angegebenen Sprache NP-vollständig sind. Können Sie einen effizienten Algorithmus erstellen? wenn ja, wird vermutet, dass es nicht NP-vollständig ist, da wir nicht glauben, dass Sprachen in P NP-vollständig sind! sonst muss man noch beweisen, dass das problem np-schwer ist!

Beachten Sie, dass es einige Probleme gibt, die wir dort nicht kennen, wie zum Beispiel den Isomorphismus von Graphen, die Berücksichtigung einer bestimmten Zahl, ... wir denken, dass diese Probleme nicht NP-vollständig sind, aber niemand könnte dies beweisen! Insbesondere haben wir Beweise dafür, dass der Graphisomorphismus nicht NP-vollständig ist! Ein weiteres Problem ist die einzigartige Spielkonjunktur, die wir für NP-vollständig halten, aber es gibt keinen Beweis dafür! Der beschriebene Ansatz ist also nicht hilfreich!

fayez abd-alrzaq taub
quelle