Zum neuen Informatik-Forum >>
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen   RegistrierenRegistrieren   ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

Hat jmd ahnung von co-NP's

 
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
SICk
Gast





BeitragVerfasst am: 16. Jan 2006 13:29    Titel: Hat jmd ahnung von co-NP's Antworten mit Zitat

Hallo, ich habe am mittwoch ein referat, über co-NP's.
Kann ir da jmd weiterhelfen????
So allgm dinge darüber, alles was ihr halt drüber wisst...
Nach oben
Tobias



Anmeldungsdatum: 15.02.2005
Beiträge: 149

BeitragVerfasst am: 16. Jan 2006 15:41    Titel: Antworten mit Zitat

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.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum nicht posten
Du kannst Dateien in diesem Forum nicht herunterladen