Mitteilungen

Hier der Link zum Complexity Zoo: Complexity Zoo
Wie in jedem guten Zoo kann man hier sicherlich Tage verbringen und hat noch nicht alles gesehen.

Hier ein Link wo diskutiert wird, welche ENTSCHEIDUNGSprobleme (wahrscheinlich) NP-schwer aber nicht NP-vollständig sind: complexity theory - NP-Hard problems that are not in NP but decidable - Computer Science Stack Exchange
Für uns am wesentlichsten ist aber, dass viele OPTIMIERUNGSprobleme NP-hard sind und (wahrscheinlich) nicht in  NP - soll heißen: wir kennen kein Zertifikat für eine Optimallösung.

Drittens: Ich stand heute in der Übung, wie Sie ja gemerkt haben, etwas auf dem Schlauch, kurz nachdem ich aus der Übung kam fiel es mir wie Schuppen aus den Haaren ;):
Wir konnten für einige der Beispielprobleme an der Tafel keine Reduktionen angeben, weil sie in coNP sind (NEIN-Instanzen haben polynomiell verifizierbare Zertifikate) - und Probleme in coNP sind (sehr wahrscheinlich) nicht NP-schwer (sondern coNP-schwer).
Um das vernünftig zu erklären, habe ich noch ein paar Folien gemacht (und bei den Vorlesungsfolien hochgeladen). Angucken ist keine Pflicht - und vermutlich auch nicht hilfreich für den Rest der Vorlesung - schauen Sie es sich an, wen nes Sie interessiert, und sonst lassen Sie es bleiben. Denn:
Für die algorithmische Praxis ist es  irrelevant, ob Probleme NP-schwer oder coNP-schwer sind: beides bedeutet, dass das Finden eines polynomiellen Lösungsalgorithmus sehr unwahrscheinlich ist - denn dieser würde auch alle anderen Probleme in NP und coNP lösen. 
Gewissermaßen war unsere 'erste' Definition von der Klasse NP zu 'ungenau'  - eine Definition aus Algorithmikersicht und ein Komplexitätstheoretiker würde sicher mit mir schimpfen. (Und sagen, dass ich Turing- und many-to-one-Reduktionen über einen Kamm schere)

Aber wie gesagt: für die Zwecke in unserer Vorlesung ist die gegebene Definition völlig in Ordnung, genauer müssen Sie es für mich nicht wissen :)