www.wikidata.de-de.nina.az
NP Schwere bezeichnet die Eigenschaft eines algorithmischen Problems mindestens so schwer losbar zu sein wie die Probleme der Klasse NP Mengendiagramm der moglichen Beziehungen zwischen P NP und den Mengen der NP schweren und NP vollstandigen Probleme Zu beachten ist dass auf der rechten Seite die leere Sprache und ihr Komplement aussen vor gelassen werden beide sind zwar in P und NP aber nicht NP schwer Die Komplexitatstheorie ein Teilgebiet der theoretischen Informatik beschaftigt sich mit der Klassifizierung von Problemen bezuglich ihrer Komplexitat d h der algorithmischen Schwierigkeit sie zu losen Eine wichtige Problemklasse ist die Komplexitatsklasse NP die Klasse der Probleme die mit einer nichtdeterministischen Turingmaschine in Polynomialzeit gelost werden konnen Anschaulich ist NP die Klasse aller Entscheidungsprobleme fur die eine gefundene Losung effizient uberpruft werden kann Ein NP schweres Problem ist nun mindestens so schwer wie alle Probleme in NP Das bedeutet dass ein Algorithmus der ein NP schweres Problem effizient also deterministisch in Polynomialzeit lost mithilfe einer Polynomialzeitreduktion genutzt werden kann um ein beliebiges Problem in NP effizient zu losen Der umgangssprachlich auftretende Begriff NP Harte ist eine Fehlubersetzung des englischen NP hard Inhaltsverzeichnis 1 Intuition 2 Definition 3 Beispiel 4 LiteraturIntuition BearbeitenUm die Schwere von Problemen zu vergleichen werden in der theoretischen Informatik Problemreduktionen benutzt Ein Problem A heisst reduzierbar auf ein anderes Problem B wenn jeder Algorithmus der B lost auch verwendet werden kann um A zu losen indem man eine Probleminstanz von A umrechnet in eine Instanz von B und diese anschliessend lost Will man durch Reduktionen Aussagen uber die Effizienz von Problemen machen ist die Effizienz der Reduktion ebenfalls wichtig Wird die Anzahl der Rechenschritte einer Reduktion in Abhangigkeit von der Eingabelange durch ein Polynom und nicht etwa durch eine Exponentialfunktion beschrieben dann wird diese Reduktion als Polynomialzeitreduktion bezeichnet Kann nun ein Problem 1 durch eine Polynomialzeitreduktion in ein Problem 2 uberfuhrt werden dessen Aufwand ebenfalls polynomial von der Eingabe abhangt so kann Problem 1 selbst in Polynomialzeit gelost werden Anfang der 1970er Jahre zeigten Stephen A Cook und Leonid Levin unabhangig voneinander dass es in NP ein Problem gibt auf das alle anderen Probleme in NP in Polynomialzeit reduziert werden konnen das Erfullbarkeitsproblem der Aussagenlogik SAT von englisch satisfiability Das Problem SAT ist also ein schwerstes Problem in NP Satz von Cook Es ist allerdings nicht das einzige schwerste Problem denn Richard M Karp zeigte dass es in NP Probleme gibt auf die SAT reduziert werden kann die also genauso schwer sind wie SAT Diese schwersten Probleme in NP werden NP vollstandig genannt Alle Probleme auch solche ausserhalb von NP die mindestens so schwer sind wie sie auf die also SAT in Polynomialzeit reduziert werden kann heissen NP schwer Definition BearbeitenSei L S displaystyle L subseteq Sigma nbsp eine formale Sprache L displaystyle L nbsp heisst dann NP schwer wenn gilt L N P L p L displaystyle forall L in rm NP L preceq rm p L nbsp Alle L displaystyle L nbsp aus NP sind polynomiell reduzierbar auf L displaystyle L nbsp Dies bedeutet dass L displaystyle L nbsp mindestens so schwer wie jedes beliebige Problem aus NP ist Diese intuitive Deutung wird gerechtfertigt durch die Tatsache dass sich mit einem Algorithmus A displaystyle A nbsp der L displaystyle L nbsp in Polynomialzeit lost fur jedes Problem aus NP ebenfalls ein polynomialer Algorithmus konstruieren liesse fuhre zuerst die Reduktion auf L displaystyle L nbsp aus und anschliessend Algorithmus A displaystyle A nbsp L displaystyle L nbsp selbst kann jedoch auch schwerer sein Insbesondere muss L displaystyle L nbsp nicht notwendigerweise in NP liegen liegt L displaystyle L nbsp jedoch zusatzlich in NP so heisst L displaystyle L nbsp NP vollstandig Beispiel BearbeitenEin klassisches Beispiel fur ein Problem das NP schwer ist und nicht in NP liegt ist das Halteproblem fur Turingmaschinen Beispielsweise lasst sich das Erfullbarkeitsproblem auf das Halteproblem reduzieren indem eine Instanz des Erfullbarkeitsproblems in eine Turingmaschine transformiert wird die nacheinander alle moglichen Belegungen durchprobiert und halt sobald eine erfullende Belegung gefunden ist andernfalls jedoch in eine Endlosschleife ubergeht Daruber hinaus liegt das Halteproblem aber selbst nicht in NP da es uberhaupt nicht entscheidbar ist Literatur BearbeitenMichael R Garey und David S Johnson Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman and Company New York 1979 ISBN 0 7167 1045 5 Kapitel 5 NP Hardness Abgerufen von https de wikipedia org w index php title NP Schwere amp oldid 236186419