Was bedeutet es, wenn ein Problem als NP-Hard betrachtet wird?
Wenn ein Problem als NP-Hard eingestuft wird, bedeutet dies, dass es mindestens genauso schwierig ist wie die schwierigsten Probleme in der Klasse der Probleme, die als NP (nicht-deterministische Polynomzeit) bekannt sind. NP-Probleme sind Entscheidungsprobleme, die in polynomischer Zeit durch eine nicht-deterministische Turing-Maschine gelöst werden können, eine hypothetische Maschine, die mehrere Lösungen gleichzeitig erforschen kann. Ein NP-Hard-Problem hingegen ist ein Problem, das mindestens genauso schwer ist wie die härtesten Probleme in NP. Mit anderen Worten, wenn ein NP-Hard-Problem in polynomischer Zeit gelöst werden könnte, dann könnten alle Probleme in NP auch in polynomischer Zeit gelöst werden. Das Konzept der NP-Hardness ist in der Informatik und Mathematik wichtig, weil es hilft, Probleme zu identifizieren, die schwer zu lösen sind. Viele Optimierungsprobleme, wie das reisende Verkäuferproblem und das Knapsackproblem, sind NP-Hard. Obwohl es derzeit nicht bekannt ist, ob diese Probleme effizient gelöst werden können, haben Forscher Algorithmen entwickelt, die in einem gewissen Grad an Genauigkeit nahelegen können.