Dieses Problem hat auch theoretischen Bedeutung, da es in die Klasse NP-vollständiger Probleme (NP-complete, NPC) gehört. NP heißt non-deterministic polynomial und bedeutet, daß diese Klasse von Problemen nur durch einen nicht-deterministischen Algorithmus in polynomialer Zeit gelöst werden kann.

Man kann es auch anders ausdrücken:
Wenn wir ein Orakel hätten, das uins an jeder Wegkreuzung den Weg sagt, der zu einem Optimum führt, sofern es diesen gibt, wären all diese Probleme in polynomialer Zeit lösbar.

Verwandte Probleme sind z.B:

• Hamiltonscher Pfad
• Rucksackproblem
• Affenpuzzel

Aber vorsicht, es gibt auch Probleme, die nur so ähnlich klingen, die aber eine polynomiale Lösung besitzen, wie der Eulersche Pfad.

Gehört der Hamiltonsche Pfad zur Klasse NPC oder nicht?

• Ja, er gehört dazu
• Nein, er gehört nicht dazu

Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996