| 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 |
