Mira94
Grünschnabel
Dabei seit: 29.10.2014
Beiträge: 3
![](images/spacer.gif) |
|
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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Mira94: 26.11.2014 12:48.
|
|