Direkt zum Inhalt

Lexikon der Mathematik: NP-vollständiges Problem

ein Problem mit der Eigenschaft, daß es für die Problemklasse C = NP und polynomielle Zeitreduktionen (polynomielle Zeitreduktion) C-vollständig ist.

Die zu sehr vielen wichtigen Optimierungsproblemen gehörigen Entscheidungsprobleme, z. B. Cliquenproblem, Rucksackproblem und TSP (Travelling-Salesman-Problem), sind NP-vollständig. Aus der Theorie der NP-Vollständigkeit folgt, daß sie und die dazugehörigen Optimierungsprobleme genau dann von polynomialen Algorithmen (polynomialer Algorithmus) gelöst werden können, wenn NP=P ist. Da die NP≠P-Hypothese gut begründet ist, gelten NP-vollständige Probleme als nicht effizient lösbar.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos