Die Abkürzung steht ja für "nicht polynomiell vollständig"….aber was bedeutet das? Kann mir da jemand weiterhelfen?
http://3773.rapidforum.com/topic=101684325186 ;)
heißt das nicht eher nichtdeterministisch polynomiell?
Nein, die abkürzung steht für Nicht-deterministisch polynomiell vollständig.
Wenn ein Problem in NP ist, heißt das erstmal, dass es eine Nicht-deterministische Turingmaschine gibt, die das Problem in polynomieller Zeit lösen kann. Das ist leider für den praktischen Fall nicht sehr hilfreich, da wir da nur deterministische Maschinen haben und die Umwandlung exponentiellen Aufwand hat. Ein Problem aus NP ist also schlimmstenfalls in der Praxis exponentiell im Aufwand.
Viele Probleme wie z.B. Zählen der Zeichen in einem Buchstaben (aufwand O(n)) ist aber auch deterministisch zu lösen in polynomieller Zeit, obwohl es trotzdem in NP liegt. Dass ein Problem in NP liegt ist also noch keine gute aussage.
Wenn man nun ein Problem in polynomieller Zeit auf unser ursprungsproblem umwandeln kann, dann sagt man polynomiell reduzierbar (afair).
Wenn nun JEDES Problem in NP auf unser Problem polynomiell reduzierbar ist, dann nennt man unser Problem NP-Vollständig.
Für die Praxis heißt das: Für dieses Problem sind auf Rechnern nur Algorithmen mit exponentiellem Aufwand bekannt und daher sind die Probleme schlecht lösbar. Weiter gilt für NP-vollständige Probleme: Findet jemals jemand für ein NP-vollständiges Problem einen deterministischen Algorithmus in polynomieller Zeit, so gibt es einen solchen algorithmus für ALLE NP-vollständigen Probleme. Es ist aber bislang nicht geklärt ob das überhuapt geht.
Findet jemals jemand für ein NP-vollständiges Problem einen deterministischen Algorithmus in polynomieller Zeit, so gibt es einen solchen algorithmus für ALLE NP-vollständigen Probleme. Es ist aber bislang nicht geklärt ob das überhuapt geht.
Es müsste heissen: "[…] für ALLE NP-Probleme […]".
Folgendes versteh ich nicht:
Viele Probleme wie z.B. Zählen der Zeichen in einem Buchstaben (aufwand O(n)) ist aber auch deterministisch zu lösen in polynomieller Zeit, obwohl es trotzdem in NP liegt.
Wenn Dein Problem in polynomieller Zeit durch eine DTM gelöst werden kann, dann liegt es ja in P. Natürlich gilt PcNP.
Nice to know: Wenn ein Problem in NP liegt ist das immernoch besser als wenn es nachweisbar exponentiell viel Zeit benötigt; da eine NTM ja im Prinzip eine Breitensuche macht, wissen wir im deterministischen Fall, daß der Baum nur bins in eine polynomielle Tiefe durchsucht werden muß.
Findet jemals jemand für ein NP-vollständiges Problem einen deterministischen Algorithmus in polynomieller Zeit, so gibt es einen solchen algorithmus für ALLE NP-vollständigen Probleme. Es ist aber bislang nicht geklärt ob das überhuapt geht.
Es müsste heissen: "[…] für ALLE NP-Probleme […]".
Ich bin für "ALLE NP-vollständigen Probleme". Denn nur diese lassen sich doch
aufeinandern zurückführen und deshalb gilt nur hier:
Eins gelöst => Alle gelöst.
Ich bin für "ALLE NP-vollständigen Probleme". Denn nur diese lassen sich doch
aufeinandern zurückführen und deshalb gilt nur hier:
Eins gelöst => Alle gelöst.
Nein, die Definition heißt, wenn sich alle Probleme aus NP auf das Problem polynomiell reduzieren lassen, ist es NP-vollständig. Also insbesondere auch alle nicht NP-vollständigen.
Da muss ich Tri zustimmen. Das habe ich selbst auch so verstanden.
Wenn man nun ein Problem in polynomieller Zeit auf unser ursprungsproblem umwandeln kann, dann sagt man polynomiell reduzierbar (afair).
Wenn nun JEDES Problem in NP auf unser Problem polynomiell reduzierbar ist, dann nennt man unser Problem NP-Vollständig.
Da fehlt noch die Voraussetzung, dass unser besagtes Problem in NP liegt (ist ja nicht zwangsläufig so. Wenn man ein Problem hat, das bewiesenermaßen schlechter als NP ist, kann man vielleicht alle Probleme aus NP polynomiell darauf reduzieren, aber es wird dadurch nicht NP-vollständig) Siehe auch Def 8.12 im Skript.
Ohne díese zusätzliche Bedingung gibt es dafür die Bezeichnung "NP-hart".
Stimmt prinzipiell, hatte Tri aber gesagt [img]
http://www.fb18.de/gfx/28.gif[/img]
