Учебники

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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