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