| Zeige Beiträge 1 bis 3 von 3 Treffern |
|
 Thema: 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
|
|
| Thema: Reduktion und Entscheidbarkeit |
|
|
Also E<gleich Q bedeutet ja, E auf Q reduzierbar ist (laut Definition). Dies ist dann der Fall, wenn x element E <-> f(x) element Q ist bzw. x element E -> f(x) element Q und x kein Element von Q -> f(x) kein Element von Q.
Mehr weiß ich leider nicht. :/
|
|
| Thema: Reduktion und Entscheidbarkeit |
|
|
Hallo, ich habe eine Aufgabe, wo folgendes gegeben ist:
Die Sprachen ((M) bezeichnet eine geeignete Kodierung der TM M über dem Alphabet Sigma.
E={(M)|L(M) = leere Menge}
Q={(M1),(M2)|L(M1)=L(M2)}
Zeigen Sie die folgende Aussage:
E<gleich Q.
Kann mir jemand sagen, wie ich das zeigen kann. Ich habe da nämliche überhaupt keine Ahnung. Bin auch relativ neu im Gebiet der TM.
Danke im Voraus
Mira94
|
|
|
| Zeige Beiträge 1 bis 3 von 3 Treffern |
|
|
|
