Deterministische vs. nichtdeterministische Berechnungen
Klasse verstehen P und NPZuerst sollten wir das Rechenmodell kennen. Daher werden wir in diesem Kapitel zwei wichtige Rechenmodelle diskutieren.
Deterministische Berechnung und die Klasse P.
Deterministische Turingmaschine
Eines dieser Modelle ist eine deterministische Einband-Turingmaschine. Diese Maschine besteht aus einer endlichen Zustandssteuerung, einem Lese- / Schreibkopf und einem Zweiwegeband mit unendlicher Sequenz.
Es folgt das schematische Diagramm einer deterministischen Einband-Turingmaschine.
Ein Programm für eine deterministische Turingmaschine gibt die folgenden Informationen an:
- Ein endlicher Satz von Bandsymbolen (Eingabesymbole und ein leeres Symbol)
- Eine endliche Menge von Zuständen
- Eine Übergangsfunktion
Wenn in der algorithmischen Analyse ein Problem in Polynomzeit durch eine deterministische Einband-Turing-Maschine lösbar ist, gehört das Problem zur P-Klasse.
Nichtdeterministische Berechnung und die Klasse NP
Nichtdeterministische Turingmaschine
Ein weiteres Modell zur Lösung des Rechenproblems ist die nicht deterministische Turingmaschine (NDTM). Die Struktur von NDTM ähnelt der von DTM, hier haben wir jedoch ein zusätzliches Modul, das als Schätzmodul bekannt ist und einem Nur-Schreib-Kopf zugeordnet ist.
Es folgt das schematische Diagramm.
Wenn das Problem durch eine nicht deterministische Turing-Maschine in Polynomzeit lösbar ist, gehört das Problem zur NP-Klasse.