[BuK] Polynomialzeitverifizierer

[Zolain]

Ahoi,

hat da noch jemand ein paar gute Aufgabenstellungen? Im Netz finde ich nur Beweise x elem NP durch Reduktionen. Es scheint fast, als hätte die RWTH die Polyzeiverifizierer für sich gepachtet. Neben den aktuellen Aufgaben hab ich nur noch die alten Aufgabenstellungen vom Lehrstuhl Vöcking. Die sind aber auch nicht so ergiebig. Für weitere Hinweise wäre ich daher dankbar.

Beste Grüße

Zol

[ZaKaRy]

Na soweit ich weiß zeigst du durch die Poly-Reduktion die NP Härte und nicht die Zugehörigkeit zu NP. Genau dafür brauch man ja Zertifikat + Verifizierer. Die meisten sagen nur, dass die Zugehörigkeit eines betrachteten Problems zu NP ist trivial ist und sparen sich den Beweis, konzentrieren sich nur auf den Beweis der NP-Härte.


Edith fügt noch einen Link ein:

http://www.logn.de/tut/ws0506/mat/

Musste dich mal durchwurschteln, besonders die letzten Übungen enthalten Aufgaben zur Berechenbarkeit !