This post has been edited 1 times, last edit by "Sebastian" (Feb 21st 2011, 6:54pm)
(glaube du hast in deiner Formel nen Tippfehler eingebaut, u<->v vertauscht).
Nur wie schon gesagt, gilt auch hier wieder für mich: darauf wäre ich NIEMALS!!! gekommen ...
blöd ist auch, dass das System gewechselt wurde, bei den Klausuren zuvor haben alle Aufgaben gezählt, haben da zuviele bestanden oder warum wurde das geändert ?
muss man hier überhaupt zeigen, d.h. mit einer Angabe eines Algorithmus', dass 2D-BIN-PACKING Element von NP ist, oder kann man einfach behaupten, das es so ist, aufgrund dessen, das 2D-BIN-PACKING eine "Unter"-Variante eines Problems(BIN-PACKING) ist, von dem man weiß, dass es Element von NP ist ?
This post has been edited 1 times, last edit by "Xular" (Feb 22nd 2011, 5:39pm)
Even-Sat hab ich ebenfalls genau so wie in der Übung gemacht, wobei mich diese Def. über der Aufgabe etwas verwirrt hat - kommt aber aufs selbe raus denk ich.
Tjo und den Supergraph hab ich wohl verkackt, hab mir da nen Zertifikat ausgesucht was H entsprach - aber das beweist ja nur NP und nicht P ... Naja, vielleicht gibts nen paar Teilpunkte. Hat mich hinterher geärgert weil eigentlich ist meine Lösung schon richtig, hätte statt H mit dem Zertifikat auszuwerten einfach H mit G auswerten müssen, hätte auch funktioniert mit dem Algo, den ich aufgeschrieben hab