Чтобы понять класс P и NP , сначала мы должны знать вычислительную модель. Следовательно, в этой главе мы обсудим две важные вычислительные модели.
Детерминированные вычисления и класс P
Детерминированная машина Тьюринга
Одной из таких моделей является детерминированная однотонная машина Тьюринга. Эта машина состоит из управления конечным состоянием, головки чтения-записи и двусторонней ленты с бесконечной последовательностью.
Ниже приведена принципиальная схема детерминированной одноленточной машины Тьюринга.
Программа для детерминированной машины Тьюринга определяет следующую информацию:
- Конечный набор символов ленты (символы ввода и пустой символ)
- Конечный набор состояний
- Функция перехода
В алгоритмическом анализе, если задача решается за полиномиальное время детерминированной ленточной машиной Тьюринга, проблема принадлежит классу P.
Недетерминированные вычисления и класс NP
Недетерминированная машина Тьюринга
Чтобы решить вычислительную задачу, другой моделью является недетерминированная машина Тьюринга (NDTM). Структура NDTM похожа на DTM, однако здесь у нас есть еще один дополнительный модуль, известный как модуль угадывания, который связан с одной головой только для записи.
Ниже приведена принципиальная схема.
Если задача решается за полиномиальное время с помощью недетерминированной машины Тьюринга, задача принадлежит классу NP.