Verifizierer < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:33 Do 10.12.2009 | | Autor: | nonne |
| Aufgabe | Ich bräuchte Ideen: Ich soll ein Zertifikat angeben um zu zeigen, dass folgende Probleme in NP liegen.
a. Partition, also die Aufteilung einer Eingabe in zwei gleich große Summen
b. Hamiltonkreis, also der Pfad in einem Graphen, der jeden Knoten genau 1x besucht
c. SAT, also das erfüllen einer KNF Formel |
Es wär echt nett, wenn mir jemand helfen könnte...ich bräuchte Ideen, Denkanstöße etc..
Danke!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:19 Fr 11.12.2009 | | Autor: | felixf |
Hallo nonne!
> Ich bräuchte Ideen: Ich soll ein Zertifikat angeben um zu
> zeigen, dass folgende Probleme in NP liegen.
Was genau soll so ein Zertifikat sein?
Normalerweise reicht es aus, einen Algorithmus anzugeben, der zu einer potentiellen Loesung in polynomieller Zeit entscheidet, ob sie korrekt ist.
Und das sollte bei diesen drei Problemen echt nicht schwer sein.
> a. Partition, also die Aufteilung einer Eingabe in zwei
> gleich große Summen
> b. Hamiltonkreis, also der Pfad in einem Graphen, der
> jeden Knoten genau 1x besucht
> c. SAT, also das erfüllen einer KNF Formel
> Es wär echt nett, wenn mir jemand helfen könnte...ich
> bräuchte Ideen, Denkanstöße etc..
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Mi 16.12.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
