в эти дни я изучаю проблемы NP, вычислительную сложность и теорию. Я считаю, что наконец понял концепции машины Тьюринга, но у меня есть пара сомнений.
Я могу согласиться с тем, что недетерминированная машина Тьюринга имеет несколько вариантов того, что делать для данного состояния и считываемого символа, и что она всегда будет выбирать лучший вариант, как указано в wikipedia.
Как НТМ «знает», какие из этих действий ему следует предпринять? Есть два взгляда на это. Один из них - сказать, что машина - «самый удачливый из возможных догадчиков»; он всегда выбирает переход, который в конечном итоге приводит к состоянию принятия, если такой переход есть. Другой - представить, что машина «разветвляется» на множество копий, каждая из которых следует одному из возможных переходов. В то время как DTM имеет единственный «путь вычисления», по которому следует, NTM имеет «дерево вычислений». Если какая-либо ветвь дерева останавливается с условием «принять», мы говорим, что NTM принимает ввод.
Что я не могу понять, так это то, что, поскольку это воображаемая машина, что мы получаем, говоря, что она может решать задачи NP за полиномиальное время? Я имею в виду, что я мог бы также теоретизировать о волшебной машине, которая решает проблемы NP в O (1), что я от этого выиграю, если она может никогда не существовать?
Заранее спасибо.
