Как делает не детерминированную работу машины Тьюринга?
Я понимаю, что они не реальны, и они, кажется, переходят вычисление каждый раз, когда существует 2 опции, вместо того, чтобы выбрать ту. Но, например, если я говорю это:
"Не детерминировано предполагают взаимно однозначное соответствие p вершин от Графика G к Графику H" (контекст вот Изоморфизм графов),
Что это, как предполагается, означает? Я понимаю взаимно однозначное соответствие, но оно говорит "не, детерминировано предполагают". Если это предполагает, как это - алгоритмический подход? Как это может гарантировать, что собирается работать?
4 ответа
Есть разные способы изображения одного. Один я нахожу полезным, это модель Oracle. Вы когда-нибудь видели мультфильм дальнего борда, где вывод на доске имеет «Здесь чудо, как один из промежуточных шагов? В этой версии NDTM, когда вам нужно что-то выбрать, Oracle записывает правильную версию на правой части ленты. (Это взято из Garey и Johnson, компьютеров и на неотложимости , их классическую книгу о проблемах NP-полных.) Вам не разрешается предполагать, что у вас есть правильный, и там не может быть правильным.
Следовательно, когда вы не детерминистически угадаете придурок, вы получаете правильный доступ для ваших целей, при условии, что существует.
Это не является хорошей основой для алгоритма, поскольку сложность внедрения недетерминированного Turging Machine в основном экспоненциальна в недетерминистских состояниях, а алгоритмический эквивалент недетерминистого предположения - попробовать все возможные придурки.
с теоретической точки зрения, я бы перевел его как «Если есть такое придурка, что ...». ». С алгоритмической точки зрения найдите другую книгу или другую главу той же книги, поскольку этот подход бесполезен для даже умеренно больших графов.
Я считаю, что означает «не определительно выбирать решение», а затем проверьте, что решение верно. Поскольку все возможные варианты (догадки) тестируются, решение гарантируется.
Физическая реализация недетерминированного Turging Machine - это компьютер ДНК. Например, вот набросок того, как решить проблему для путешествий в ДНК:
Получить / сделать кучу последовательностей ДНК, каждая с длиной пропорциональна стоимости края в вашем графике и липких концах с последовательностями уникально вершин, которые краевые соединяются.
Смешайте их вместе, с ДНК-лигазой в большом стакане. Они отжигают друг другу в последовательностях, которые представляют все возможные пути через график (OK, а не на самом деле длинные).
Удалите все последовательности, которые отсутствуют хотя бы одну вершину. Для этого последовательно выберите для каждой вершины, используя гибридизацию. Например, если «ACGTACA» кодирует вершину 1, выберите для последовательностей, которые связываются с «TGTACGA». Затем повторите этот выбор для любой другой вершины.
Сортируйте оставшиеся последовательности по размеру с использованием гелевого электрофореза. Затем последовательность самый короткий. Последовательность кодирует кратчайший путь через ваш график.
Это не так, они просто иллюстрируют суть. В основном, они угадывают ответ и проверяют, правильный ли он (детерминированно). Однако важно не угадывание ответа, а проверка правильности ответа. Это все равно, что сказать: если дать произвольное решение, будет ли оно правильным? Например, есть задачи, вычисление которых занимает экспоненциальное время, и некоторые из их ответов можно проверить за полиномиальное время, а некоторые - нет. Так вот, недетерминированный ТМ разделяет эти две задачи: те, которые можно быстро проверить, и те, которые нельзя. И тут возникает вопрос: если одна группа решений вопросов может быть проверена намного быстрее, чем другая, то могут ли их решения также быть сгенерированы быстрее? На этот вопрос пока нет ответа.