Выдержка из книги
Иванов В.В.
Методы вычислений на ЭВМ Справочное пособие
Ключевое понятие в теории NP-полных задач - НМТ [16], для которых каждый шаг может иметь конечное число различных продолжений. При данном входном слове X можно считать, что НМТ М параллельно выполняет все возможные последовательности шагов, пока не достигнет заключительного ( допускающего) состояния ( в этом случае X называется допускаемым) или пока не окажется, что дальнейшие шаги невозможны. Если а - кратчайшая последовательность шагов, которая оканчивается допускающим состоянием, то, как только машина М сделает о шагов, она остановится. Часто удобно представлять, что М угадывает только шаги из последовательности а. Поэтому естественно ожидать, что НМТ способны выполнять задания, которые никакие детерминированные машины Тьюринга не могут выполнить за то же время или с той же памятью.
![Ключевое понятие в теории NP-полных задач - НМТ [16], для которых каждый шаг может иметь конечное число различных продолжений. При данном входном слове X можно считать, что НМТ М параллельно выполняет все возможные последовательности шагов, пока не достигнет заключительного ( допускающего) состояния ( в этом случае X называется допускаемым) или пока не окажется, что дальнейшие шаги невозможны. Если а - кратчайшая последовательность шагов, которая оканчивается допускающим состоянием, то, как только машина М сделает о шагов, она остановится. Часто удобно представлять, что М угадывает только шаги из последовательности а. Поэтому естественно ожидать, что НМТ способны выполнять задания, которые никакие детерминированные машины Тьюринга не могут выполнить за то же время или с той же памятью.](/pic/2548468T3j2sMN0002291160.png)