b): Erklärung der grundsätzlichen Vorgehensweise?

Question

Könnte mir jemand bei Aufgabenteil b) bitte die grundsätzliche Vorgehensweise erklären?

Mir ist klar, dass es sich hierbei um das Traveling Salesman Problem handelt, aber wie kann man sich logisch erklären, dass dieses NP-vollständig ist?

Und woher weis ich dann, dass der Zeitaufwand mindestens exponentiell ist?

Vielen Dank

Answer 1

Hallo,

in der Vorlesung (Foliensatz 5 Folie 41) wurden bei der Definition der NP-Vollständigkeit Probleme aufgelistet, die NP-vollständig sind (wozu auch TSP gehört). 

Die Beweise dass u.a. TSP NP-vollständig ist kann man in der Literatur nachlesen. Garey und Johnson wurden als Authoren genannt.

Mit der Vermutung auf der folgenden Seite im Skript; dass es keinen Algorithmus gibt, der NP-vollständige Probleme in polynomieller Zeit löst; sollte auch Ihre letzte Frage geklärt sein.

Gruß,

Alexander (Tutor)