---

Geschrieben von JROppenheimer am 22.03.2008 um 09:46:

  P-NP-Einführung

Ich hab dummerweise das Vorhaben, ein Seminar in Theo zu machen. Jetzt habe ich mein Thema bekommen und (wie alle anderen auch) gehts hauptsächlich um fundamentale Komplexitätsprobleme.

Jetzt stehe ich vor dem Problem, dass ich von P und NP zero Ahnung habe ...

Hätte vlt. einer eien Empfehlung, wie ich mich am besten in das Thema reinarbeite?! Vlt kennt einer eine gute möglichst nicht zu ausführliche Einführung in das Thema, oder kann mir das knapp zusammenfassen, damit ich mit den ganzen Abkürzungen was anfangen kann: P, NP, FNP, FP sowas...

Danke Euch allen schon mal im Voraus!

---

Geschrieben von Tobias am 22.03.2008 um 12:13:

 

Das ist aber ein weites Feld. Wie kommts, dass du davon garkeine Ahnung hast?

Ich würde mit diversen Wikipedia-Artikeln anfangen:

http://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie
http://de.wikipedia.org/wiki/NP_%28Komplexit%C3%A4tsklasse%29
http://de.wikipedia.org/wiki/P-NP-Problem
http://de.wikipedia.org/wiki/Karps_21_NP-vollst%C3%A4ndige_Probleme
http://qwiki.stanford.edu/wiki/Complexity_Zoo#{{{2}}}

Hast du kein genaueres Thema bekommen?

---

Geschrieben von JROppenheimer am 23.03.2008 um 12:43:

 

Ich studiere ja Informatik auf Dipl. Bei uns sind aber alle Dipl. Vorlesungen schon durch Bachelorvorlesungen ersetzt. Da wird das alles etwas anders gelehrt... Theo2 habe ich genau bis zu den regulären Ausdrücken geschafft. Da mangelte es mir an Zeit und letztes Semester habe ich mich mit Algorithmentheorie auseinander gesetzt ... (brauche ja einen theoäquivalenten Schein) Da gings aber erst gegen Ende um P-NP und das Zeug. Da es mir aber an Lerngruppen mangelt und ich mir versuche das alles per Bücher und Übungen beizubringen fehlt mir einfach das Wissen. Und ich dachte ich käme vlt drum herum, mir erst die ganze Sache mit den Turing Maschinen anzuschauen, ich würde nämlich gern möglichst schnell zum eigendlichen "Problem" kommen ohne vorher lange Zeit an Vorbereitung zu verlieren.

Der Titel des Beitrags, über den ich referieren soll ist: "On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence"

Geht irgendwie um die Einführung neuer Komplexitätsklassen bin aber nicht sicher...