NP-Vollständigkeit |
| 19.02.2014, 15:43 | 9ool09 | Auf diesen Beitrag antworten » | ||
| NP-Vollständigkeit Hallo, ich schreibe demnächst eine Klausur in Optimierung und ein großer Teil der Klausur wird sich um Komplexitätstheorie drehen. Ich denke mal es geht um NP-Vollständigkeits Beweise. Meine Ideen: Ich komme mit dem Thema leider nicht wirklich klar. Das Grundprinzip ist klar, aber die Konstruktion herzuleiten erscheint mir doch eher Glückssache zu sein. Wie kann ich mich darauf gut vorbereiten? |
||||
| 19.02.2014, 15:46 | Math1986 | Auf diesen Beitrag antworten » | ||
| RE: NP-Vollständigkeit Hast du dir denn mal Beispiele dazu angesehen? Welche Probleme sind NP-vollständig und welche nicht, und mit welcher begründung? |
||||
| 19.02.2014, 16:34 | 9ool09 | Auf diesen Beitrag antworten » | ||
Hi, ja kenne einige Beispiele. Es läuft immer so, dass man ein schon bekanntes NP-vollständiges Problem auf das zu beweisende Problem zurückführt. |
||||
| 19.02.2014, 17:51 | Math1986 | Auf diesen Beitrag antworten » | ||
|
||||
| 19.02.2014, 19:05 | 9ool09 | Auf diesen Beitrag antworten » | ||
Ich kann sie ruhig posten, aber sie helfen mir nicht wirklich, wenn ich dann eine Aufgabe hab wo die Konstruktion komplett anders läuft. Beispiele: 3SAT < SAT Stabile Menge < Vertex Cover Vertex Cover < Feedback Vertex Set Hamiltonkreis |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
