Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2012-N-05 https://info2.aifb.kit.edu/qa/index.php?qa=qa&qa_1=2012-nachklausur&qa_2=2012-n-05 Powered by Question2Answer Beantwortet: b): Erklärung der grundsätzlichen Vorgehensweise? https://info2.aifb.kit.edu/qa/index.php?qa=2808&qa_1=b-erkl%C3%A4rung-der-grunds%C3%A4tzlichen-vorgehensweise&show=2809#a2809 <div class="ilFrmPostContent"> <p> Hallo,</p> <p> 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).&nbsp;</p> <p> Die Beweise dass u.a. TSP NP-vollständig ist kann man in der Literatur nachlesen. Garey und Johnson wurden als Authoren genannt.</p> <p> 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.</p> <p> Gruß,</p> <p> Alexander (Tutor)</p> </div> <p> &nbsp;</p> 2012-N-05 https://info2.aifb.kit.edu/qa/index.php?qa=2808&qa_1=b-erkl%C3%A4rung-der-grunds%C3%A4tzlichen-vorgehensweise&show=2809#a2809 Fri, 25 Sep 2015 13:54:40 +0000