Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

alternative Argumentation, sodass clique_mod-c NP Schwierig?

+1 Punkt
133 Aufrufe

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

 

Gefragt 29, Sep 2015 in 2011-N-05 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

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 29, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...