Имеет ли P = NP в клеточных автоматах гиперболических пространств?
Несколько лет назад я прочитал в этой книге, что задачи NP решаются в пространстве клеточных автоматов на гиперболической плоскости . Что это значит? Соответствует ли P = NPсогласно этим книгам / бумагам?
Некоторые выдержки из статьи:
Хорошо известно, что если в нашем распоряжении есть бинарные деревья «бесплатно», то можно решать NP-задачи за полиномиальное время, см. [14, 5]. Однако реализовать алгоритмы двоичного дерева в пентаграде не сразу, и цель этого раздела - указать, как можно действовать дальше.
Насколько я понимаю, проблема P = NP заключается в поиске алгоритмов с полиномиальным временем для решения сложных проблем. Беглый взгляд на книги и статьи показывает, что он решил проблему. Что мне не хватает?
Вот еще одна статья, озаглавленная « В некоторых искривленных пространствах. Мы можем решить NP-трудные задачи за полиномиальное время: к мечте Матиясевича» .
Ответы
Проблема P vs. NP - это вопрос о машинах Тьюринга. $T$, потому что классы сложности P и NP определены в терминах этих теоретических машин. Назовем эти классы$P_T$ а также $NP_T$впредь. В статье представлена новая теоретическая вычислительная машина.$H$ с ассоциированными классами $P_H$ (выполняется за полиномиальное время на гиперболическом клеточном автомате) и $NP_H$ (выполняется за недетерминированное полиномиальное время на гиперболическом клеточном автомате).
Первым шагом в этой статье является доказательство того, что проблема 3SAT, хорошо известная $NP_T$-полная задача, может быть решена за полиномиальное время на этой машине, т.е. $P_H$. Затем они показывают, что любое полиномиальное сокращение времени на машине Тьюринга может быть выполнено за полиномиальное время на их гиперболическом автомате. Поскольку 3SAT$NP_T$-полный, любой $NP_T$ экземпляр может быть уменьшен до экземпляра 3SAT за полиномиальное время (на $T$ по определению, так же и $H$по их лемме), а затем решается путем решения 3SAT за поливремени, как на гиперболическом автомате. Другими словами, основной результат статьи (теорема 1) можно записать в виде$NP_T \subseteq P_H$в наших обозначениях. Это не дает решения проблемы P vs. NP, потому что для этого потребуется связать классы$NP_T$ а также $P_T$.
Обратите внимание, что авторы включают некоторые замечания по проблеме P vs. NP в разделе 4.2, где они утверждают, что их результат является доказательством P$\neq$НП (!):
Третье направление состоит в новом освещении вопроса P = NP в обычных условиях. Поскольку гиперболическое пространство имеет свойства, которые сильно отличаются от свойств евклидова пространства, в частности, у него гораздо больше направлений, не будет ли это намеком, благоприятным для доказательства того, что P$\neq$НП в евклидовых условиях? Кажется, что последние десять лет работы в области сложности склоняют людей больше верить в П.$\neq$Н.П. Видимо, нынешний результат тоже относится к этой тенденции.