Каковы последствия того, что недетерминированная машина Тьюринга может решить NP за полиномиальное время?

Question

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

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

Как NTM «узнает», какое из этих действий оно должно предпринять?Есть два способа посмотреть на это.Нужно сказать, что машина - «самый удачливый догадчик»;он всегда выбирает переход, который в конечном итоге приводит к принимающему состоянию, если такой переход существует.Другой - представить, что машина «разветвляется» на множество копий, каждая из которых следует за одним из возможных переходов.В то время как DTM имеет единственный «путь вычисления», которому он следует, NTM имеет «дерево вычислений».Если какая-либо ветвь дерева останавливается с условием «принять», мы говорим, что NTM принимает ввод.

Что я не могу понять, так как это воображаемая машина, что мы получаемСказать, что он может решить проблемы NP в полиномиальное время?Я имею в виду, я мог бы также теоретизировать магическую машину, которая решает проблемы NP в O (1), что я получу от этого, если она может никогда не существовать?

Заранее спасибо.

Answer 1

Недетерминированная машина Тьюринга - сложная концепция для понимания. Попробуйте другие точки зрения:

1. Вместо запуска волшебной машины Тьюринга, которая является самым удачным догадчиком, запустите еще более волшебную метамашину, которая устанавливает бесконечное число случайно угадывающих независимых машин Тьюринга в параллельных вселенных. Каждая возможная последовательность догадок сделана в некоторой вселенной. Если хотя бы в одной из юниверсов машина останавливается и принимает ввод, этого достаточно: экземпляр проблемы принимается мета-машиной, которая настроила эти параллельные юниверсы. Если во всех юниверсах машина отклоняет или не останавливается, метамашин отклоняет экземпляр.

2. Вместо каких-либо предположений или разветвлений, представьте себе, как один человек пытается убедить другого в том, что этот случай должен быть принят. Первый человек предоставляет набор вариантов, которые должны быть сделаны недетерминированной машиной Тьюринга, а второй - проверяет, принимает ли машина данные с этими вариантами. Если это так, второй человек убежден; если это не так, первый человек потерпел неудачу (что может быть вызвано тем, что экземпляр не может быть принят с какой-либо последовательностью выборов, или потому что первый человек выбрал неправильную последовательность выборов).

3. Забудьте о машинах Тьюринга. Проблема в NP, если ее можно описать формулой в экзистенциальной логике второго порядка . То есть вы берете логическую пропозициональную логику, разрешаете любые квантификаторы над пропозициональными переменными и разрешаете вначале использовать экзистенциальные квантификаторы над множествами, отношениями и функциями. Например, трехцветность графа можно описать формулой, которая начинается с экзистенциальной количественной оценки по цветам (наборам узлов):

   & существует; R & Существуют; G & Существуют; B

   Каждый узел должен быть окрашен:

   & существует; R & Существуют; G & Существуют; B (& x27; x (R (x) & or; G (x) & or; B (x)))

   и никакие два соседних узла не могут иметь одинаковый цвет & ndash; вызвать отношение ребер E:

   * * & Тысяча тридцать-один существует; R & Существуют; G & Существуют; B (& x27; x (R (x) & or; G (x) & or; B (x))) & and; (& xom; x, y & not; (E (x, y) & and; ((R (x) & and; R (y)) & or; (G (x) & and; G (y)) & or; (B (x ) & и; B (у)))))

   Экзистенциальная квантификация по переменным второго порядка подобна недетерминированной машине Тьюринга, дающей совершенные догадки. Если вы хотите убедить кого-то в том, что формула существует; X (...) верно, вы можете начать с задания значения X. То, что NTM за полиномиальное время и эти формулы не просто «похожи», но фактически эквивалентны, является теоремой Фейгина, которая положила начало области описательной сложности : классы сложности, характеризуемые не машинами Тьюринга, а классами логических формул.

Вы также сказали

Я мог бы также теоретизировать магическую машину, которая решает проблемы NP в O (1)

Да, вы можете. Они называются оракулами (никакого отношения к СУБД), и они дали интересные результаты в теории сложности. Например, теорема Бейкера - Джилла - Соловая гласит, что существуют оракулы A и B, такие что для машин Тьюринга, которые имеют доступ к A, P = NP, но для машин Тьюринга, которые имеют доступ к B, P & ne; NP. (A - очень мощный оракул, который делает недетерминизм несущественным; определение B немного сложнее и включает в себя уловку диагонализации.) Это своего рода мета-результат: любое доказательство, решающее вопрос P vs NP, должно быть чувствительным Для определения машины Тьюринга достаточно того, что он выходит из строя при добавлении некоторых оракулов.

---

Ценность недетерминированных машин Тьюринга в том, что они предлагают сравнительно простую вычислительную характеристику класса сложности NP (и других): вместо деревьев вычислений или логических формул второго порядка вы можете подумать о почти обычном компьютере это было (сравнительно) немного изменено, так что это может сделать идеальные догадки.

Answer 2

Вы получаете от этого то, что вы можете доказать, что проблема в NP, доказав, что она может быть решена NTM за полиномиальное время.

Другими словами, вы можете использовать NTM, чтобы узнать, есть ли данная проблема в NP или нет.

Answer 3

По определению, NP означает недетерминированное полиномиальное время, которое можно найти в Википедии .

Воплощении недетерминированной машины Тьюринга, которая случайным образом выбирает и исследует (или собирает) следующуюпотенциальное решение с некоторой вероятностью решит проблему NP за полиномиальное время (если бы оно было «самым удачливым догадчиком», то оно решило бы задачу за многократное время).

Следовательно, говоря, что NTM может решить проблему за полиномиальное время эффективно означает, что эта проблема находится в NP.Это снова эквивалентно определению класса проблем NP.

Answer 4

Я думаю, что ваш ответ в вашем вопросе. Другими словами, если у вас есть проблема, вы можете доказать, что это проблема NP, если вы можете найти NTM, который ее решает.

Проблемы NP - это особый класс проблем, а NTM - это всего лишь инструмент для проверки, принадлежит ли данная проблема классу.

Обратите внимание, что NTM не является конкретной машиной - это целый класс машин с четко определенными правилами того, что они могут и не могут делать. Чтобы использовать «магические» машины, вам нужно определить их и показать, какому классу сложности они соответствуют.

См. http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes для получения дополнительной информации.

Answer 5

То, что мы получаем, это то, что , если у нас есть магическая сила, чтобы угадать правильный шаг, который всегда будет правильным, мы можем решить проблемы NPC в ПОЛИТИКЕ. Конечно, мы не всегда можем «угадать» правильный шаг. Так что это мнимая. Но так же, как мнимые числа применимы к проблемам реального мира, последствия могут быть теоретически полезны.

Один положительный аспект превращения исходных проблем таким образом заключается в том, что мы можем решать их с разных сторон. В теоретической области это хорошо, потому что у нас есть (1) больше подходов, которые мы можем использовать (таким образом, больше статей) и (2) больше инструментов, которые мы можем использовать, если их можно сформулировать в других областях.

Answer 6

Из еврейской Википедии - «NTM - это, в основном, инструмент для размышлений, и на самом деле такую ​​машину невозможно реализовать». Вы можете заменить термин «NTM» на «Алгоритм, который на каждом шаге пробует все возможные шаги» или «Алгоритм, который на каждом шаге выбирает наилучший возможный следующий шаг». И я думаю, вы понимаете все остальное. NTM здесь только для того, чтобы помочь нам визуализировать такой алгоритм. Вы можете увидеть здесь , как это должно помочь вам визуализировать (в ответе Паскаля Куока).