Auswahl Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
| Autor |
  NP vs. Co-NP |
|
ChristophR
Aktiv 
Dabei seit: 11.03.2011
Mitteilungen: 34
Aus:
 |      Themenstart: 2012-03-14 12:23
|
Hallo!
Co-P = P, weil man statt des Co-Problems einfach das zugehörige P-Problem lösen und dann das Ergebnis negieren kann.
Wieso kann man nicht für Co-NP vs. NP genauso argumentieren? Also etwa für UNSAT (Co-NP-complete): Entscheide SAT mittels NP-Maschine und negiere das Ergebnis.
Sorry für die Frage, eigentlich wusste ich das und wenn man die Probleme als Sprachen sieht ist es klar, dass sie nicht unbedingt unter Komplementbildung abgeschlossen sind. Aber ich habe für Co-P und P gerade obigen Satz gelesen und stehe jetzt im Falle von NP irendwie neben mir.
Danke schonmal!
|
 Profil
 Quote
 Link |
Bilbo
Senior 
Dabei seit: 03.01.2005
Mitteilungen: 1748
Aus:
 | Beitrag No.1, eingetragen 2012-03-14 12:42
|
Hallo ChristophR,
das Problem liegt in der Assymetrie des Akzeptanzverhaltens von nichtdeterministischen Turingmaschinen. Ein Wort wird akzeptiert, wenn es eine akzeptierende Rechnung gibt, aber es wird verworfen, wenn alle Rechnungen es verwerfen (und nicht etwa, wenn es eine verwerfende Rechnung gibt).
Wenn man also zum Beispiel zwei mögliche Rechenpfade hat, einer davon akzeptierend und einer verwerfend, und man negiert jeweils deren Ergebnisse, dann ist immer noch ein Pfad akzeptierend und einer verwerfend. Damit würde das vorher akzeptierte Wort dann immer noch akzeptiert.
Viele Grüße,
Thorsten
-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel
[Verschoben aus Forum 'Logik, Mengen & Beweistechnik' in Forum 'Komplexitätstheorie' von Bilbo]
|
Profil
Quote
Link |
ChristophR
Aktiv
Dabei seit: 11.03.2011
Mitteilungen: 34
Aus:
| Beitrag No.2, vom Themenstarter, eingetragen 2012-03-14 12:47
|
Das war mir soweit klar. Ich meinte allerdings auch nicht dass das Ergebnis pro Rechenpfad negiert wird sondern insgesamt.
D.h.: 1. Gegen sei eine UNSAT-Instanz. 2. Löse dafür das SAT-Problem durch Ausführen einer NP-Maschine. 3. Wenn ein Pfad akzeptierend ist, gib false zurück, sonst wahr.
Um zu zeigen dass ein NP- und ein Co-NP-Orakel gleich mächtig sind, wird doch genauso argumentiert. Die Frage ist nur, wieso funktioniert das nur bei Oraklen (d.h. bei Delta_2^P), nicht aber bei NP/Co-NP.
|
Profil
Quote
Link |
Bilbo
Senior
Dabei seit: 03.01.2005
Mitteilungen: 1748
Aus:
| Beitrag No.3, eingetragen 2012-03-14 12:57
|
Hallo Christoph,
wenn du das so machen willst, dann musst du aber ja alle Rechenpfade darauf überprüfen, ob einer davon akzeptierend ist. Da es exponentiell viele Pfade geben kann, ist dein Algorithmus dann nicht mehr polynomialzeitbeschränkt.
Viele Grüße,
Thorsten
-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel
|
Profil
Quote
Link |
ChristophR
Aktiv
Dabei seit: 11.03.2011
Mitteilungen: 34
Aus:
| Beitrag No.4, vom Themenstarter, eingetragen 2012-03-14 13:00
|
Danke, das hab ich vergessen, jetzt ist alles wieder klar.
LG
|
Profil
Quote
Link |
|
Wie unterstütze ich den Matheplaneten mit Geld?
[Neues Thema]