Die Klassen P und NP

Zeitkomplexität des Euler-Problems und des Hamilton-Problems

Die Zeitkomplexität eines Problems wird durch eine untere Schranke für Kostenfunktionen von Algorithmen zur Lösung des Problems beschrieben.

Oft ist man nicht in der Lage, solche Schranken für Kostenfunktionen anzugeben. Man beschränkt sich dann darauf, das Problem einer Komplexitätsklasse zuzuordnen.

Beim Euler-Problem haben wir gezeigt, dass es mit einem Algorithmus mit quadratischer Zeitkomplexität gelöst werden kann. Das Euler-Problem gehört also zur Klasse P der Probleme, die mit einem polynomialen Algorithmus gelöst werden können.

Anders verhält es sich beim Hamilton-Problem. Die beiden hier vorgestellten Lösungsalgorithmen haben eine exponentielle Zeitkomplexität. Alle weiteren Lösungsalgorithmen, die bisher entwickelt worden sind, haben ebenfalls eine exponentielle Zeitkomplexität. Ob es Lösungsalgorithmen für das Hamilton-Problem gibt, die eine polynomiale Zeitkomplexität aufweisen, ist nicht bekannt. Es ist also noch offen, ob das Hamilton-Problem zur Klasse P gehört oder nicht. Man vermutet aufgrund der vielen negativen Ergebnisse, dass es wohl nicht zu P gehört.

Nicht-deterministische Algorithmen mit polynomialer Komplexität

Interessante Ergebnisse erhält man, wenn man den Algorithmusbegriff etwas aufweicht. Bei einem Algorithmus haben wir bisher immer vorausgesetzt, dass er deterministisch in dem Sinne ist, dass der nächste Ausführungsschritt immer genau feststeht. Wenn man diese Voraussetzung weglässt, gelangt man zu den nichtdeterministen Algorithmen. Es zeigt sich, dass sich etliche Probleme mit noch nicht geklärter Komplexität mit nichtdeterministischen Algorithmen lösen lassen, die eine polynomiale Komplexität haben. Zu diesen Problemen gehört auch das Hamilton-Problem.

Wir verdeutlichen im Folgenden, dass das Hamilton-Problem mit einem polynomialen nichtdeterministischen Algorithmus gelöst werden kann.

ALGORITHMUS hamiltonkreis_nichtdeterministisch
    Übergabe: Graph, dargestellt mit Nachbarschaftslisten
    # erzeuge nichtdeterministisch einen Rundreisekandidaten
    lege einen startKnoten fest
    weg = [startknoten]
    n = Anzahl der Knoten des Graphen
    restKnoten = Liste mit allen Knoten außer dem startKnoten
    WIEDERHOLE n-1 mal:
        naechsterKnoten = erratener Wert aus restKnoten[0] | restKnoten[1] | ... | restKnoten[n-2]
        weg = weg + [naechsterKnoten]
    weg = weg + [startKnoten]
    # überprüfe den Rundreisekandidaten
    hamiltonkreisExistiert = True
    FÜR i von 1 BIS n-1:
        WENN weg[i] kein Nachbar von weg[i-1] ist oder
             weg[i] bereits in [weg[0], ..., weg[i-1]] vorkommt:
            hamiltonkreisExistiert = False
    WENN weg[n] kein Nachbar von weg[n-1] ist:
        hamiltonkreisExistiert = False
    Rückgabe: hamiltonkreisExistiert

Die nichtdeterministische Stelle im Algorithmus ist die Zuweisung naechsterKnoten = erratener Wert aus restKnoten[0] | restKnoten[1] | ... | restKnoten[n-2]. Der senkrechte Strich soll hier bedeuten, dass entweder restKnoten[0] oder restKnoten[1] oder ... oder restKnoten[n-2] als erratener Wert bei der Zuweisung genommen wird. Hier ist also nicht eindeutig festgelegt, welche Zuweisung zum Zuge kommt.

Der nichtdeterministische Algorithmus hat eine polynomiale Komplexität. Bei der (nichtdeterministischen) Erzeugung des Weges wird die Liste weg insgesamt n-mal erweitert. Bei der Überprüfung des Weges muss n-mal getestet werden, ob aufeinanderfolgende Knoten eine Kante des Graphen bilden. Hierzu muss jeweils maximal n-mal getestet werden, ob ein Knoten nicht bereits unter den Vorgängerknoten des Weges vorkommt. Insgesamt ergibt sich eine quadratische Komplexität.

Das Hamilton-Problem gehört also zur Klasse NP aller Probleme, die mit einem nichtdeterministischen Algorithmus mit polynomialer Komplexität gelöst werden können.

Nichtdeterministische Algorithmen werden in der Praxis nicht benutzt - hier muss immer alles eindeutig geregelt sein. Warum solche nichtdeterminischen Algorithmen dennoch interessant sind, soll im nächsten Abschnitt geklärt werden.