Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 9
Наверное сразу стоит оговорить, что данный результат не означает решения проблемы. Ведь постановка этой проблемы не «решить задачу
за
времени», а можно ли симулировать недетерминированную машину Тьюринга на обычной машине Тьюринга за полином времени.
На самом деле, если вы решаете одну NP-полную задачу за полином то сразу же решаете и ВСЕ NP задачи за полином. Причем в этой же модели вычислений, как я понимаю, раз она симулирует МТ. А если даже нет — на практике как раз свести (за полином) одну NP задачу к некоторой NP-полной совсем не проблема.
Поправьте если я не прав.
Все правильно за одним исключением: данная модель, при решении задач, не симулирует МТ (приведенная теорема была для иллюстрации того, что она в принципе может это делать). Она решает задачи, скажем так, по-своему.
В том и проблема равенства классов NP и P, что есть модели вычислений, которые решают NP полные задачи за полином (та же недетерминированная машина Тьюринга), но реализовать на практике мы(пока что) можем только обычную машину Тьюринга. Поэтому есть, вообще говоря два выхода из положения. Понять как решать быстро задачи на МТ, либо предложить хорошую модель, которую мы сможем построить в нашей реальности.
В том и проблема равенства классов NP и P, что есть модели вычислений, которые решают NP полные задачи за полином (та же недетерминированная машина Тьюринга), но реализовать на практике мы
Похоже на продолжение идеи клеточных автоматов.
Похоже на продолжение идеи клеточных автоматов.
Интересно, а с мемристорами как элементной базой идея мемпроцессоров как-нибудь состыковывается?
Выглядит любопытно, но я несколько не понял:
«задачи из класса NP полных задач за полином времени и памяти.»
Полином по памяти — это очень плохо. NP \in PSPACE
Ну, и вторая проблема в том, что даже обычную машину тьюринга мы не можем сделать, потому что у неё по условию бесконечная лента, и это условие нельзя ослабить.
Правильно я понимаю, что у мемристорной машины для имитации бесконечной ленты требуется бесконечное число мемпроцессоров?
«задачи из класса NP полных задач за полином времени и памяти.»
Полином по памяти — это очень плохо. NP \in PSPACE
Ну, и вторая проблема в том, что даже обычную машину тьюринга мы не можем сделать, потому что у неё по условию бесконечная лента, и это условие нельзя ослабить.
Правильно я понимаю, что у мемристорной машины для имитации бесконечной ленты требуется бесконечное число мемпроцессоров?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Universal Memcomputing Machines как альтернатива Машине Тьюринга