Hi!
Zitat:
|
Ich denke aber, dass das Problem des Handlungsreisenden kein NP- vollständiges Problem ist, sondern lediglich ein NP Problem.
|
Möglicherweise ist es nur ein P-Problem. Meines Wissen gibt es hier in der Mathematik unterschiedliche Auffassungen. Einmal hier:
http://lexikon.meyers.de/meyers/Spez...easerID=100340, wonach das "Problem des Handlungsreisenden" als NP-Problem dargestellt wird, - andererseits finde ich plausibler, dass dies nur ein 'P-Problem' ist, da es in 'vernünftiger Zeit' proportional zu n-Rechenschritten offenbar zu lösen ist, wie richy bereits erwähnt hat. Primzahlfaktorisierungen würden hier demgegenüber wahre NP-Probleme darstellen, da die erforderlichen Rechenschritte hier exponentiell zunehmen.
Ein 'NP-Vollständiges Problem' wäre demnach ein Algorithmus der das Faktorisierungsproblem löst. Und so einer ist nicht bekannt.