Diskussion:Co-NP

Der Satz ist zwar wortreich, aber auch sinnlos:

Wenn A NP-vollständig ist, dh. A in NP und NP = CoNP, dann ist A trivialerweise auch in CoNP. Ich denke aber, dass = hier nicht gleich = ist, sondern eher das typische von-hinten-durchs-Knie-ins-Auge-reduziert-Istgleich; was dem Umstand keinen Abbruch tut, dass das was dasteht keine nichttriviale Formulierung benötigt.

NP-vollständige Probleme sind nicht bekannt, die in co-NP zu liegen. Deine Folgerung geht so also nicht. --Shurakai 18:54, 27. Jan. 2009 (CET)

„Wenn ein Problem sowohl in NP als auch in Co-NP enthalten ist, so wird allgemein angenommen, dass es nicht NP-vollständig ist” – Gibt es Probleme, von denen bekannt ist, dass sie in NP liegen aber nicht NP-vollständig sind? Wäre es möglich ggf. ein Beispiel anzugeben? -- octo 18:58, 9. Apr. 2009 (CEST)

Gibt es Probleme, von denen bekannt ist, dass sie in NP liegen aber nicht NP-vollständig sind? Wäre es möglich ggf. ein Beispiel anzugeben?

Da P eine Teilmenge von NP ist, sind auch alle Probleme von P in NP. Die sind natürlich nicht NP-Vollständig. Das zu schreiben wäre aber nicht sinnvoll. NP-Vollständige Probleme sind sozusagen die schwersten in NP. Alle leichteren sind natürlich trotzdem in NP. Anonymous (nicht signierter Beitrag von 91.57.108.119 (Diskussion | Beiträge) 00:26, 16. Jun. 2009 (CEST))

Okay, für Probleme in P gilt das natürlich trivialerweise. Die Frage zielte eigentlich auf nicht-triviale Fälle ab, also Probleme, die in NP und Co-NP liegen, von denen man aber nicht weiß, ob sie in P liegen. Viele Grüße, -- octo 10:32, 16. Jun. 2009 (CEST)

Graphisomorphie ist vermutlich so ein Problem. Es gibt (bisher) keinen polynomialzeit Algo für Graphisomorphie, aber falls Graphisomorphie NP-vollständig ist bricht die polynomielle Hierarchie auf der zweiten Stufe zusammen. 89.244.113.198 20:21, 6. Mai 2011 (CEST)

Struktur

Die Struktur des Artikels sollte überarbeitet werden; Primzahltest sollte beispielsweise raus und eher noch einige nette Eigenschaften von co-NP beschrieben werden (z.B. die Beziehung zur Polynomialhierarchie usw.) --Shurakai 18:54, 27. Jan. 2009 (CET)

Ich würde auch empfehlen den Primzahltest zu löschen, ich kann eine Relevanz zu co-NP nur schwer erkennen. Andreschulz (Diskussion) 09:34, 25. Apr. 2013 (CEST)

TAUTOLOGIE ist das Komplement von SAT

Stehe ich völlig auf dem Schlauch oder ist das nicht korrekt? Das Komplement von SAT sollte doch sowas wie "PARADOXIE" sein (keine Ahnung, ob es diesen Namen gibt), also die Menge aller Formeln, die nicht erfüllbar sind. --Ccoenig (Diskussion) 15:21, 12. Jul. 2013 (CEST)

In der Tat, das ist unglücklich ausgedrückt (um es mal vorsichtig zu sagen). Was gemeint ist, eine Formel φ ist genau dann erfüllbar, wenn die Negation von φ eine Tautologie ist. Ich ändere das gleich mal um .... --Andreschulz (Diskussion) 18:40, 13. Jul. 2013 (CEST)

Deterministisch ?

In der Einleitung steht, dass co-NP die Klasse der Sprachen ist usw usw "dass ein Wort nicht zur Sprache gehört, deterministisch in Polynomialzeit durch eine Turingmaschine überprüft werden kann". Wäre es nicht korrekter zu schreiben: "...in Polynomialzeit durch eine NICHT-deterministische Turingmaschine..." ? --194.95.69.150 15:23, 5. Mär. 2014 (CET)

Nein, die Verifikation geschieht in der Tat durch eine deterministische Turing-Maschine in polynomieller Zeit. --Andreschulz (Diskussion) 23:11, 5. Mär. 2014 (CET)

Komisch, in der englischen WP lese ich „co-NP is the set of decision problems where the "no" instances can be accepted in polynomial time by a non-deterministic Turing machine.“. Ist das nun auch falsch, oder habe ich es nicht verstanden? --H.Marxen (Diskussion) 17:51, 20. Jun. 2014 (CEST)

Nein, das ist nicht komisch. Es gibt verschiedene (äquivalente) Definitionen für die Klasse NP: eine davon beruht auf "VERIFIKATION in polynomieller Zeit mit einer deterministischen TM", die andere auf "ERKENNEN der Sprache in polynomieller Zeit durch eine Nichtdeterministische TM". Daraus leiten sich dann auch "unterschiedliche" Definitionen für die Klasse Co-NP ab. Das steht aber alles im Artikel. --Andreschulz (Diskussion) 11:47, 21. Jun. 2014 (CEST)

Danke für die erneute Erläuterung. Ist offenbar für Nicht-Experten schwierig die formalen Feinheiten sauber auseinander zu halten. --H.Marxen (Diskussion) 15:37, 23. Jun. 2014 (CEST)

Formale Definition

An der Stelle

"Äquivalent kann man für den ersten Punkt fordern, dass $x\in L\iff \forall y\colon M(x,y)=1$."

ist es meine Meinung nach falsch $M(x,y)=1$ zu fordern, schließlich ist das nicht das gleiche wie in der Aussage vorher. Die angegebene Quelle macht, meiner Meinung, an der Stelle auch einen (Flüchtigkeits-)Fehler. Und zwar steht dort, "$x\not \in L\iff \exists y\colon M(x,y)=1$ ist das gleiche wie $x\in L\iff \forall y\colon M(x,y)=0$. Wir können aber die Ausgabe von $M$ umdrehen und $M'$ bekommen." Danach müssten sie aber $M'(x,y)=1$ schreibt statt $M$. JonasCleve (Diskussion) 00:20, 18. Mai 2016 (CEST)

Das ist schon richtig so. Ob man nun $M$ oder $M'$ schreibt macht keinen wirklichen Unterschied. Denn wichtig ist ja nur wie die Maschine quantifiziert ist. Also ob man nun schreibt $\exists M\colon x\in L\iff \forall y\colon M(x,y)=1$ oder $\exists M'\colon x\in L\iff \forall y\colon M'(x,y)=1$ - egal. Das $M$ aus der einen Definition ist unabhängig vom $M$ aus der anderen. --Andreschulz (Diskussion) 21:06, 24. Mai 2016 (CEST)