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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
200 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

 

in 2011-N-05 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...