Tobias
Anmeldungsdatum: 15.02.2005 Beiträge: 149
|
Verfasst am: 16. Jan 2006 15:41 Titel: |
|
|
coNP ist die Menge aller Sprachen, deren Komplement in NP liegt.
Wenn man eine Sprache gegeben hat kann man also in polynomieller Zeit nichtdeterministisch entscheiden, ob ein Wort w nicht in L liegt: .
Ebenso wie zu NP gibt es auch coNP-vollständige Sprachen. Dies sind Sprachen, auf die sich alle anderen coNP-Sprachen in Polynomialzeit reduzieren lassen. Es gilt weiterhin (so meine ich mich zu erinnern) die Beziehung:
L NP-vollst. <=> L^C coNP-vollst.
coNP und NP sind nicht disjunkt. D.h. wenn man eine NP-vollständige Sprache L findet, die auch in coNP liegt, so haben wir NP = coNP bewiesen. Es wird jedoch vermutet, dass die Mengen nicht gleich sind. Hier handelt es sich aber wieder um ein unbewiesenes Problem.
Falls man irgendwann mal beweisen sollte, dass P = NP, dann gilt automatisch auch coNP = NP, denn P ist unter Komplementen abgeschlossen. Aus coNP = NP folgt jedoch nicht automatisch P = NP. Ferner ist P Teilmenge von coNP. |
|