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.