NP-vollständig (theoretische Informatik)

grundlegender Begriff der Komplexitätstheorie, der eine Menge von besonders schwierigen Entscheidungsproblemen aus der Komplexitätsklasse NP klassifiziert, die sich vermutlich nicht effizient lösen lassen. Der Begriff wurde 1971 von dem amerikanischen Informatiker Stephen Cook (*1939) geprägt. Um die NP-Vollständigkeit eines Problems nachzuweisen, muss man zunächst zeigen, dass dieses in der