---

Geschrieben von Mira94 am 26.11.2014 um 12:44:

  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