UniqueSAT Co-Np |
| 26.11.2014, 12:44 | Auf diesen Beitrag antworten » |
| Mira94 | UniqueSAT Co-Np Hallo, ich soll beweisen, dass Unique-Sat co-np schwer ist. Laut Definition gilt ja: Eine Sprache ist co-np vollständig, wenn folgende 2 Bedingungen gelten: 1.Sprache L ist selbst aus Co-Np 2. Für jede Sprache A € co-np gibt es eine polynomielle Reduktion von A auf L. Gilt nur das 2. so ist bewiesen, das das Problem co-np schwer ist. Kann jemand mir Schritt für Schritt helfen, dieses Problem zu lösen. Ich verstehe es nämlich überhaupt nicht. 
Danke Mira 94 |
|
|
|
|
|