Diskussion:Co-NP

Letzter Kommentar: vor 8 Jahren von Andreschulz in Abschnitt Formale Definition

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)Beantworten

„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)Beantworten

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)) Beantworten

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)Beantworten
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)Beantworten

Struktur

Bearbeiten

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)Beantworten

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)Beantworten

TAUTOLOGIE ist das Komplement von SAT

Bearbeiten

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)Beantworten

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)Beantworten

Deterministisch ?

Bearbeiten

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)Beantworten

Nein, die Verifikation geschieht in der Tat durch eine deterministische Turing-Maschine in polynomieller Zeit. --Andreschulz (Diskussion) 23:11, 5. Mär. 2014 (CET)Beantworten
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)Beantworten
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)Beantworten
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)Beantworten

Formale Definition

Bearbeiten

An der Stelle

"Äquivalent kann man für den ersten Punkt fordern, dass  .[1]"

ist es meine Meinung nach falsch   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, "  ist das gleiche wie  . Wir können aber die Ausgabe von   umdrehen und   bekommen." Danach müssten sie aber   schreibt statt  . JonasCleve (Diskussion) 00:20, 18. Mai 2016 (CEST)Beantworten

Das ist schon richtig so. Ob man nun   oder   schreibt macht keinen wirklichen Unterschied. Denn wichtig ist ja nur wie die Maschine quantifiziert ist. Also ob man nun schreibt   oder   - egal. Das   aus der einen Definition ist unabhängig vom   aus der anderen. --Andreschulz (Diskussion) 21:06, 24. Mai 2016 (CEST)Beantworten
  1. Boaz Barak: NP completeness,CoNP, the Polynomial Hierarchy and P/poly (lecture notes). (pdf; 174 kB) Abgerufen am 26. April 2013.