Fachrat Informatik - Forum

Naja, ein genaues System gibt es nicht, du musst halt schauen, ob es ein Problem gibt, was deinem irgendwie ähnlich ist....
Wenn du eine aussagenlog. Formel hast, dann kommen ja gewöhnlich nur die SAT-Probleme in Frage (SAT, Double-SAT, 3-SAT, EVEN-SAT...). Bei den Grafik-Sachen, musst du halt schauen, was für Sachen du in deinem Problem gegeben hast und danach dann das Problem auswählen, mit dem du arbeiten willst. Wir hatten da ja so einige... CLIQUE, VERTEX-COVER usw.
Du musst halt diese Probleme alle kennen und dir dann dein Problem anschauen. Wenn du irgendeine Parallele findest, dann versuchst du die Reduktion mit diesem Problem und hast dann (hoffentlich) gewonnen

Quoted from "cartman"

wenn ich zeigen will, dass ein gegebenes problem np-hart ist, so muss man es ja auf ein auf problem aus dem oben genannten schaubild reduzieren,

Nein, so genau nicht! Wenn Du zeigen willst, dass ein Problem A NP-hart ist, kannst Du ein NP-hartes Problem B nehmen und dieses B auf A reduzieren, also zeigen, dass gilt. Was Du beschrieben hast, also ein Problem A auf ein Problem B aus dem Schaubild (die alle ja NP-vollständig und damit auch NP-hart sind) reduzieren, in Zeichen zeigen, würde beweisen, dass A in NP liegt. Das ist ein wichtiger Unterschied!

Quoted from "cartman"

gibts es da ein system hinter, auf welches problem genau man reduzieren muss ?

Auch hier wieder formulierst Du es falsch herum. Du solltest fragen, *von welchem* Problem man genau reduzieren muss.
Wenn ein gegebenes Problem A NP-hart ist, dann ist klar, dass Du prinzipiell alle Probleme aus NP darauf reduzieren könntest. Häufig ist die Überlegung von welchem Problem man die Reduktion starten möchte, gar nicht so einfach. Aber sos1981 hat das schon ganz gut beschrieben.
In der Regel empfiehlt es sich, dass man es mit Problemen versucht, die ähnliche Eingabeinstanzen haben. Wenn also A ein Problem über Graphen ist, dann sollte man überlegen, ob man eine Idee dazu hat, wie man eins der einem bekannten NP-vollständigen Probleme, die mit Graphen zu tun haben, auf A reduzieren könnte. Haut davon nichts hin, sollte man vielleicht überlegen, ob man eventuell etwas konzeptfremdere Probleme wie z.B. 3SAT darauf reduzieren könnte. Wenn alles nicht hilft, muss man schließlich darüber nachdenken, wie man eine generische Reduktion hinbekommen könnte. Eine generische Reduktion habt ihr z.B. beim Satz von Cook kennengelernt. Das ist eine Reduktion bei der man das Wortproblem für eine TM die eine beliebige Sprache aus NP löst, auf A reduziert.
Abschließend sei aber noch bemerkt, dass in der Klausur solche Wege bis zum letzten Schritt nicht verlangt werden. Wenn die NP-vollständige Sprache von der aus auf das gegebene A reduziert möglichst werden sollte sehr offensichtlich ist, dann wird das eine der ersten Kandiaten mit ähnlichen Eingabeinstanzen sein. Ansonsten wird der "Reduktionspartner" direkt von uns vorgegeben. Ich hoffe das ganze war jetzt verständlich genug.

Es geht in diesen Aufgaben darum, die Sätze, die in der Vorlesung bewiesen wurden, anzuwenden. Also solltest du, wenn du sie nicht im Kopf hast, diese dir nochmal anschaun.
in Aufgabe 2 wurde zuerst der Schritt auf 1,5^n gemacht, um dann mit nem Hierachiesatz weitermachen zu können.
Hoffe das hilft,
Henning

Dann auch mal von mir eine Frage:

Zu der Aufgabe EVEN-SAT:={<p> | p ist erfüllbar und hat eine gerade Anzahl an erfüllenden Belegungen}.
Zeigen Sie, dass EVEN-SAT NP-vollständig ist.

Mein Problem ist, dass wenn mein Zertifikat ,,die gerade Anzahl der erfüllenden Belegungen ist"
Meine Eingabe also mein p und mein Zertifikat ist.
Ich prüfe also, ob ,,Formels" mit dieser Belegung erfüllt sind und ob es eine gerade Anzahl ist.
Wenn ja, scheint alles gut, doch es könnte ja immer noch sein, dass es eine weitere Belegung gibt für die das gilt.
Sprich ich eigentlich um ganz sicher zu gehen, dass es ,,nur" eine gerade Anzahl von Belegungen gibt, alle möglichen Belegungen durchgehen müsste, was jedoch nicht in polynomieller Zeit geht.

Anders gefragt, kann ich einfach damit zufrieden sein, eine gerade Anzahl gefunden zu haben und selbst wenn es eine weitere Belegung gibt, dann interessiert es mich nicht, da meine Lösung eine Untermenge quasi davon wäre?

Dazu mal ne Frage, wo hast du die Lösungen her? Finde nix im stud.IP.

Quoted from "Soul"

Zu der Aufgabe EVEN-SAT:={<p> | p ist erfüllbar und hat eine gerade Anzahl an erfüllenden Belegungen}.

EVEN-SAT ist auch nur lediglich NP-hart und nicht in NP enthalten.

@ Arne, aber in der Klausur (WS 07) lautet die Frage zu zeigen, dass es NP-vollständig ist.
Dazu muss es doch in NP enthalten sein, oder versteh ich was falsch, bzw. sollte man in der Klausur zu so einer Schlussfolgerung kommen?

Quoted from "Soul"

@ Arne, aber in der Klausur (WS 07) lautet die Frage zu zeigen, dass es NP-vollständig ist.
Dazu muss es doch in NP enthalten sein, oder versteh ich was falsch, bzw. sollte man in der Klausur zu so einer Schlussfolgerung kommen?

In der Klausur wurde damals angesagt, dass die Aufgabenstellung diesbezüglich auf nur NP-Härte geändert wird.

Ah, ok danke konnte ich ja nicht wissen

Übung 8 ist die Aufgabe auch noch mal mit dem Verweis auf die Klausur

So mal eine andere Frage:
Hab gehört, dass es möglich wäre auch eine mündlche Prüfung zu ,,erbitten", wenn man schon einige Male durchgefallen ist.
Wie sieht das den jetzt genau aus, sprich wie oft müsste man durchgefallen sein und mit wem müsste man das dann klären?

Ich verweise mal auf: Ausnahmen Studienabschluss
Da steht alles drin, was man wissen muss.

Viele Grüße,
jasinai

Hallo,

wie schreibt man eine Reduktion formal korrekt auf?
Kann mal jemand so'n Grundgerüst aufschreiben?

Möchte ja nicht wegen formalen Fehlern Punktabzug bekommen.


Danke.

Siehe http://www.thi.uni-hannover.de/fileadmin…erloesungen.pdf Aufgabe 2.

Quoted from "Arne"

EVEN-SAT ist auch nur lediglich NP-hart und nicht in NP enthalten.

Kannst du das beweisen?

Sofern ungleich NP ist, ja.