alternative Argumentation, sodass clique_mod-c NP Schwierig?

Question

hier eine kleine überlegung, könnte man nicht so argumentieren dass clique_mod-c NP Schwierig ist?

- clique ist polynomiell reduzzierbar auf SAT

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

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

- (k-c) SAT ist element NP Schwer da SAT element NP ist, daher ist auch clique element NP SChwer

 

so wo ist hier jz der Denkfehler? :D

 

Answer 1

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)