Was ist NP-schwer?

NP-schwer (Englisch "NP-hard") nennt man eine bestimmte Klasse von algorithmischen Problemen, für die bislang noch niemand eine schnelle Lösung gefunden hat. NP bedeutet dabei "Nichtdeterministisch Polynomiell". Dieses Video versucht, die Grundideen hinter zentralen Konzepten der algorithmischen Komplexitätstheorie zu vermitteln, ohne dabei den langen und anstrengenden Weg über nichtdeterministische Turingmaschinen und komplizierte Beweise zu gehen.

00:00 - Intro
00:19 - Kameraüberwachung von Graphen
01:29 - Vertex Cover Problem
02:52 - Brute Force Lösung
06:05 - Komplexitätsklasse vs. Laufzeitklasse
07:48 - Eingabelänge vs. Eingabegröße
09:36 - Komplexitätsklasse P = Polynomiell
11:57 - Nichtdeterminismus = Orakel
14:56 - Komplexitätsklasse NP = Nichtdeterministisch Polynomiell
15:46 - P = NP?
18:29 - NP-schwer
24:20 - Hamiltonpfadproblem vs. Eulerpfadproblem
26:16 - Beweisen, dass ein Problem NP-schwer ist
28:09 - Überblick: Methoden, mit NP-schweren Problemen umzugehen
30:01 - Vertex Cover Parametrisieren

Beispiele für den Umgang mit NP-schweren Problemen:
- Traveling Salesman Problem: https://youtu.be/bRVARQ0s3dw
- Rucksackproblem: https://youtu.be/CiX_eG0dXBo