Делает P= NP в клеточных автоматах гиперболических пространств?

Question

Я прочитал несколько лет назад в Эта книга , которая NP Проблемы проводятся в пространстве клеточных автоматов в гиперболической плоскости . Что это значит? Делает P = NP в соответствии с этими книгами / бумагами?

Некоторые выдержки из бумаги:

Хорошо известно, что если у нас есть двоичные деревья в нашем распоряжении «бесплатно», можно решить NP-проблемы в полиноме, см. [14, 5]. Тем не менее, нельзя реализовывать алгоритмы двоичных деревьев в Pentagrid, а цель этого раздела - указать, как можно продолжить.

Из моего понимания, p= np Проблема ищет алгоритмы многочлена-времени для решать сложные проблемы. Из моего курсового взгляда через книги и бумаги, кажется, предполагает, что он решил проблему. Что мне не хватает?

Здесь это еще одна бумага, названная в некоторых изогнутых пространствах, мы Может решать проблемы с трудом NP-труда в многочленом времени: в направлении мечты Мьясевича .

Answer 1

Проблема P vs. NP - это вопрос о Turing Machines $ T $ , поскольку классы сложности P и NP определены в терминах этих теоретических машин. Давайте назовем эти классы $ p_t $ и $ np_t $ Отныне. В статье представлены новые теоретические вычислительные машины $ h $ , которые имеют соответствующие классы $ p_h $ (работает в полиноме Время на гиперболическом сотовом автомате) и $ np_h $ (работает в нетерминированном многочленом времени на гиперболическом сотовом автомате).

Первым шагом в этой статье является доказательством, что проблема 3SAT, хорошо известная $ NP_T $ - Проблема, может быть решена в многочленом времени на этой машине , т.е. эта проблема заключается в $ p_h $ . Далее они показывают, что какое-либо многочренное сокращение времени на машине Turging может быть выполнено в многочленом времени на их гиперболическом автомате. Поскольку 3sat - $ np_t $ - queplete, любой экземпляр $ NP_T $ может быть уменьшен до экземпляра 3SAT в Polynomial Time (на $ T $ по определению, так и на $ h $ по их лемме), а затем Быть решенным путем решения 3SAT в Poly-Time, как на гиперболическом автомате. Другими словами, основным результатом этой статьи (теорема 1) может быть записан как $ NP_T \ SOUNTED P_H $ в нашей записи. Это не дает решения задачи P VS. NP, потому что это необходимо будет связать классы $ np_t $ и $ P_t $ .

Обратите внимание, что авторы включают некоторые замечания на проблему P vs. NP в разделе 4.2, где они утверждают, что их результат - доказательство p $ \ NEQ $ NP ( !):

Третье направление состоит из нового света, пролив на вопрос P= NP в Обычные настройки. Поскольку гиперболическое пространство имеет свойства, которые очень отличаются от свойств евклидовых пространств, в частности, у него есть много других направлений, не будет подсказкой, благоприятным для доказательства того, что P $ \ neq $ np в евклидовых условиях? Кажется, что За последние десять лет работы в области сложности склонны людей верить Подробнее в P $ \ NEQ $ np. По-видимому, настоящий результат также принадлежит этой тенденции.