Obliczenia deterministyczne a obliczenia niedeterministyczne
Zrozumieć klasę P i NP, najpierw powinniśmy znać model obliczeniowy. Dlatego w tym rozdziale omówimy dwa ważne modele obliczeniowe.
Obliczenia deterministyczne i klasa P.
Deterministyczna maszyna Turinga
Jednym z tych modeli jest deterministyczna maszyna Turinga z jedną taśmą. Maszyna ta składa się ze skończonej kontroli stanu, głowicy odczytująco-zapisującej i dwukierunkowej taśmy z nieskończoną sekwencją.
Poniżej znajduje się schematyczny diagram deterministycznej maszyny Turinga z jedną taśmą.
Program dla deterministycznej maszyny Turinga określa następujące informacje -
- Skończony zestaw symboli taśmy (symbole wejściowe i pusty symbol)
- Skończony zbiór stanów
- Funkcja przejścia
W analizie algorytmicznej, jeśli problem jest rozwiązany w czasie wielomianowym przez deterministyczną maszynę Turinga z jedną taśmą, to problem należy do klasy P.
Obliczenia niedeterministyczne i klasa NP
Niedeterministyczna maszyna Turinga
Aby rozwiązać problem obliczeniowy, innym modelem jest niedeterministyczna maszyna Turinga (NDTM). Struktura NDTM jest podobna do DTM, jednak tutaj mamy jeden dodatkowy moduł zwany modułem zgadywania, który jest powiązany z jedną głowicą tylko do zapisu.
Poniżej znajduje się schemat ideowy.
Jeśli problem można rozwiązać w czasie wielomianowym przez niedeterministyczną maszynę Turinga, to problem należy do klasy NP.