Seit 1971 wird an folgender Frage geforscht:

P = NP ?

Das bedeutet, gehören polynomiale Probleme und nicht-deterministisch polynomiale Probleme in die selbe Problemklasse? Wenn dem so ist, wären auch die Probleme aus NPC in polynomialer Zeit lösbar. Vermutet wird, daß die Ungleichheit gilt, aber es konnte bisher nicht bewiesen werden.

Schwierigkeiten hat man auch mit der Primzahlzerlegung, von der man zwar weiß, daß sie zu NP gehört, man kann (konnte) aber nicht zeigen, daß sie zu NPC gehört. Es konnte keine Transformation gefunden werden.

Es ist wichtig zu verstehen, daß es Probleme gibt, auf die wir noch keine Antwort wissen. Wenn sich also noch jemand an der Lösung versuchen möchte ...?

TSP & NPC Homepage Lösungsansätze

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