Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


45. NP-vollständige Probleme



Übungen

  1. Erstellen Sie ein Programm für die Bestimmung des längsten einfachen Pfades von x nach y in einem gegebenen gewichteten Graph.
  2. Könnte ein Algorithmus existieren, der ein NP-vollständiges Problem in einer durchschnittlichen Zeit von N log N löst, falls P <> NP gilt? Begründen Sie Ihre Antwort.
  3. Geben Sie einen nichtdeterministischen, polynomiale Zeit erfordernden Algorithmus zur Lösung des Zerlegungsproblems an.
  4. Ist eine unmittelbare Reduktion des Problems des Handlungsreisenden für Graphen auf das Euklidische Problem des Handlungsreisenden in polynomialer Zeit möglich, oder umgekehrt?
  5. Was würde ein Programm bedeuten, das das Problem des Handlungsreisenden in einer zu 1,1N proportionalen Zeit lösen kann?
  6. Ist die in diesem Kapitel angegebene logische Formel erfüllbar?
  7. Könnte einer der »algorithmischen Automaten« mit völliger Parallelität verwendet werden, um ein NP-vollständiges Problem in polynomialer Zeit zu lösen, falls P <> NP gilt? Begründen Sie Ihre Antwort.
  8. Wie läßt sich das Problem »Berechnung des exakten Wertes von 2N« in das Schema der Klassifikation P-NP einordnen?
  9. Beweisen Sie unter Benutzung der NP-Vollständigkeit des Problems des Hamilton-Zyklus für ungerichtete Graphen, daß das Problem der Bestimmung eines Hamilton-Zyklus in einem gerichteten Graph NP-vollständig ist.
  10. Angenommen, für zwei Probleme sei bekannt, daß sie NP-vollständig sind. Folgt daraus, daß eine Reduktion des einen Problems auf das andere in polynomialer Zeit möglich ist, falls P <> NP gilt?


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]