Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSonntag, 27. Mai 2012 

NP-Vollständigkeit


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Achtung: Dieser Artikel setzt Fachwissen voraus welches nicht in Kürze dargelegt werden kann. Der sollte zum Verständnis wenigstens mit den Begriffen Turingmaschine Entscheidungsproblem Algorithmus Polynomialzeit-Algorithmus Polynomialzeit-Reduktion und formale Sprache ausreichend vertraut sein.
Der Begriff NP-Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der theoretischen Informatik . Er klassifiziert eine Menge von Entscheidungsproblemen die in gewisser Hinsicht besonders schwierig und für die angenommen wird dass keine effizienten Algorithmen existieren die diese lösen.

Siehe auch : P/NP-Problem

Inhaltsverzeichnis

Definition

Ein Problem (genauer: ein Entscheidungsproblem ) L heißt NP-vollständig genau dann wenn

  1. <math>L \in NP</math>
  2. Es gibt eine Polynomialzeitreduktion aller Probleme in NP auf L (vgl. NP-Schwere )

Genau so wird dies natürlich nicht häufig für konkrete Probleme gezeigt weil es schwierig ist eine Aussage für beliebige Probleme NP zu zeigen. Vielmehr nimmt man ein für das die NP-Vollständigkeit schon bekannt ist reduziert es auf dasjenige Problem für das die Eigenschaft der NP-Vollständigkeit zeigen will. Aus Transitivität von Polynomialzeitreduktionen folgt dann dass alle Probleme aus NP auch auf das betrachtete Problem reduzierbar

Klassische Vertreter NP-vollständiger Probleme sind etwa

NP-Äquivalenz

Der Begriff NP-Vollständigkeit ist nur für Entscheidungsprobleme definiert also Probleme die sich auf das Wortproblem einer Sprache zurückführen lassen. Für Optimierungsprobleme und Suchprobleme gibt es den Begriff der NP-Äquivalenz.

Approximation

Probleme die in NP liegen lassen weiter in ihrer Komplexität unterteilen je nach wie gut sie sich approximativ lösen lassen. Das Graphen-Färbungsproblem läßt sich nur sehr schlecht approximativ lösen während andere beliebig gut mittels so genannten Approximationsschemata approximieren

Starke und schwache NP-Vollständigkeit

Weiter kann man die NP-vollständigen Probleme einteilen in

  • stark NP-vollständige und
  • schwach NP-vollständige Probleme

Bleibt das Problem auch noch mit Kodierung der Eingabe NP-vollständig so heißt das stark NP-vollständig ansonsten schwach NP-vollständig . Eine alternative Definition besagt dass es schwach NP-vollständige Probleme so genannte pseudopolynomielle Algorithmen gibt für stark NP-vollständige Probleme dagegen nicht. Algorithmen bei denen der Laufzeitschranke eine Zahl vorkommt die nicht von der Eingabelänge abhängt nennt man pseudopolynomiell da die Laufzeit nicht zwangsläufig polynomiell muss - etwa wenn diese Zahl so wird dass sie exponentiell in der Eingabelänge

Lösungsansätze

Probleme dieser Problemklasse haben die unangenehme dass die Rechenzeit bei zunehmender Datenmenge rasch astronomische steigt. Eine vollständige und optimale Lösung daher bestenfalls für kleine Datenmengen zu erreichen. Rahmen der Software-Entwicklung folgt man drei Lösungsansätzen ein solches Problem anzuprogrammieren:

  1. Man schreibt tatsächlich einen optimalen Algorithmus geht davon aus dass die zu verarbeitende Datenmenge in einem Bereich bleibt der klein genug um die Lösung abzuwarten.
  2. Man wählt einen heuristischen Algorithmus also ein System und sucht nicht nach einer optimalen sondern nur nach einer Lösung die für konkrete Aufgabe gut genug ist.
  3. Man wählt einen approximativen Algorithmus der die perfekte Lösung aber eine nahezu perfekte bietet.

Siehe auch: NP (Komplexitätsklasse) Komplexitätsklasse




Bücher zum Thema NP-Vollständigkeit

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/NP-vollst%E4ndig.html">NP-Vollständigkeit </a>