Beantwortet: alternative Argumentation, sodass clique_mod-c NP Schwierig?

Tue, 29 Sep 2015 08:27:29 +0000

Ich tue mich extrem schwer, deine Argumentation nachzuvollziehen, daher hier ein paar Anmerkungen zu den einzelnen Schritten

- clique ist polynomiell reduzzierbar auf SAT

ok, das folgt aus clique \( \in \) NP und SAT ist NP-vollständig

- clique mit k Knoten ist polynomiell reduzzierbar auf k-SAT

Wie kommst du darauf? Ich weiß ehrlich gesagt nicht, ob das wahr ist. Vermutlich ja, Beweisidee:

clique mit k Knoten auf clique reduzieren, dann auf k-SAT (ist für \( k \geq 3\) NP-Vollständig)

- clique ist k-c Knoten ist polynomiell reduzzierbar auf (k-c)-SAT

folgt aus der (zweifelhaften) zweiten Aussage.

- (k-c) SAT ist \( \in \) NP Schwer da SAT \( \in \) NP

Ich verstehe nicht, wie du hier argumentierst. Das ist für k-c=2 falsch, falls P \( \ne \) NP gilt (2-SAT liegt in P)

OK, (k-c) SAT ist für \( k - c \geq 3 \) NP-vollständig, aber das lässt sich nicht ohne weiteres aus SAT \in NP folgern.

- daher ist auch clique \( \in \) NP Schwer [ich vermute, du meinst \( clique_{mod-c}\) . dass clique NP-Schwer ist, folgt sofort aus clique NP-Vollständig (laut Aufgabenstellung) ]

Daraus, dass ich ein Problem X auf ein NP-Schweres Problem polynomiell reduzieren kann, folgt nicht, dass das Problem X auch NP-Schwer ist. Gegenbeispiel Sortieren einer Liste von Zahlen:

Mergesort hat Komplexität O(n log n) -> Sortieren liegt in P
Daher muss Sortieren auf SAT reduzierbar sein (Def. von NP-Vollständig)
Wenn Sortieren NP-Schwer ist, dann kann man (wegen SAT \( \in \) NP und der Def. von NP-Schwer) SAT polynomiell auf Sortieren reduzieren -> wir haben einen Algorithmus, der SAT deterministisch in Polynomialzeit löst (!), also P = NP
falls \( P \ne NP \) gilt, entsteht ein Widerspruch.

Schau dir lieber nochmal die Definition von NP-Schwer an und achte darauf, dass deine Argumentation auch für andere verständlich und nachvollziehbar bleibt.

Du musst genau andersherum argumentieren: indem du ein bekanntermaßen NP-Schweres Problem auf das zu untersuchende Problem reduzierst, nicht umgekehrt!

Ich hoffe, du kannst mit meinen Anmerkungen etwas anfangen...

Gruß,

Tobias (Tutor)

Beantwortet: b): Was bedeutet das "feste" k genau?

Tue, 29 Sep 2015 08:18:47 +0000

Hallo,

die Antwort von Tobias ist vollkommen richtig und zeigt die mathematische Seite, aber vielleicht kann ich noch ein bisschen zum intuitiven Verständnis beitragen.

Wenn wir uns vorstellen, dass konstant k=10 gilt, dann ist es vielleicht ein intuitiv "schwieriges" Problem, in einem Graphen mit vielleicht n=30 Knoten nach einer Clique mit 10 Knoten zu suchen - das ist nicht anders als wenn wir das normale Clique-Problem auf diesen Graphen anwenden und k=10 setzen. Der Unterschied ist aber in der relativen Schwierigkeit, wenn die Knotenzahl n steigt (denn wir betrachten ja normalerweise den ZeitZUWACHS bei steigender Eingabelänge). Wenn wir in einem Graphen mit n=1000 nach einer Clique mit 10 Knoten suchen, dann ist das k verhältnismäßig klein und führt insgesamt zu einem nur polynomiellen Zuwachs der Laufzeit: \( O(n^k \cdot k^2) \). Ist das k nicht konstant, dann kann es mit n wachsen und wir erhalten beispielsweise mit \( k=\frac{n}{2}: O(n^{\frac{n}{2}} \cdot (\frac{n}{2})^2)\), was nicht mehr polynomiell ist.

(Das ist übrigens kein Beweis dafür, dass Clique ein schwieriges Problem ist, sondern nur eine obere Schranke. Sonst würde man ja noch schlimmere Komplexität bekommen, wenn man \(k=n\) oder noch größer setzt, aber stattdessen wird es wieder leichter, wenn sich k der Knotenanzahl n annähert. Will man zeigen, dass Clique schwer ist, muss man eine Reduktion durchführen.)

Viele Grüße

Lukas König

Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2011-N-05

Beantwortet: alternative Argumentation, sodass clique_mod-c NP Schwierig?

Beantwortet: b): Was bedeutet das "feste" k genau?