Детерминированные и недетерминированные вычисления

Чтобы понять класс P и NP, сначала мы должны знать вычислительную модель. Следовательно, в этой главе мы обсудим две важные вычислительные модели.

Детерминированные вычисления и класс P

Детерминированная машина Тьюринга

Одна из таких моделей - детерминированная одноленточная машина Тьюринга. Эта машина состоит из конечного управления, головки чтения-записи и двусторонней ленты с бесконечной последовательностью.

Ниже приводится схематическая диаграмма детерминированной однопленочной машины Тьюринга.

Программа для детерминированной машины Тьюринга определяет следующую информацию:

  • Конечный набор символов ленты (входные символы и пустой символ)
  • Конечный набор состояний
  • Функция перехода

В алгоритмическом анализе, если проблема решается за полиномиальное время с помощью детерминированной однопленочной машины Тьюринга, проблема принадлежит к классу P.

Недетерминированные вычисления и класс NP

Недетерминированная машина Тьюринга

Для решения вычислительной задачи еще одной моделью является недетерминированная машина Тьюринга (NDTM). Структура NDTM аналогична DTM, однако здесь у нас есть один дополнительный модуль, известный как модуль предположения, который связан с одной головкой только для записи.

Ниже приведена принципиальная схема.

Если проблема решается за полиномиальное время с помощью недетерминированной машины Тьюринга, проблема принадлежит к классу NP.