Test

Struktur usw.

Leider hab ich keine Möglichkeit Code hier zu Posten. Also werde ich eine Seite wie Pastebin benutzen um Beispiele einzufügen.

Beispiel - NP-vollständigkeit

Ein NP-vollständiges Problem zeichnet sich durch Zwei Eigenschaften aus:

1. Das Problem liegt in NP
2. Alle anderen Probleme in NP lassen sich in polynomieller Zeit auf dieses Problem Reduzieren (NP-hart)

Das Hamiltonkreisproblem liegt in NP

Um zu sehen, ob ein Problem in NP liegt kann ein Algorithmus gefunden werden, der zu einer Eingabe der Problems ein Polynomiell abhängiges Zertifikat überprüft, welches beschreibt, ob die Eingabe lösbar ist.

In diesem Fall ist die Eingabe des Problems ein kodierter Graph. Das Zertifikat beschreibt einen Möglichen Kantenzug über alle Knoten des Graphen. Dieser ist natürlich von der Länge der Eingabe abhängig.

Um zu Prüfen, ob ein Kantenzug (hier von `s` nach `t`) wirklich durch alle Knoten genau einmal geht, muss nur mit jedem Schritt des Kantenzuges die Existenz der Kante getestet und der neue Knoten in eine Menge von Knoten aufgenommen werden. Wenn kein Knoten doppelt eingefügt und am Ende alle Knoten Elemente der Menge sind, dann wurde ein möglicher Kantenzug nachgewiesen. Das Durchlaufen der Menge und das Einfügen der Elemente in die Menge ist jeweils Polynomiell von der Anzahl der Knoten abhängig.

Für das Hamiltonkreisproblem müsste noch getestet werden, ob der Start und Endknoten gleich sind, was auch in Polynomieller Zeit möglich ist.