Действительно ли Memcomputing решает NP-полную проблему?

9

Я наткнулся на статью, опубликованную в Science, «Memcomputing NP-полных задач за полиномиальное время с использованием полиномиальных ресурсов и коллективных состояний» , в которой содержатся довольно удивительные утверждения.

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

(Курсив мой).

Я бы отмахнулся от этого как от несерьезного, учитывая сильный характер утверждений, если бы не тот факт, что это было опубликовано в «Науке», и что соответствующий материал некоторых авторов был опубликован в « Физике природы» , в журнале IEEE и в Physics Review E , все из которых являются авторитетными рецензируемыми публикациями, которые не позволили бы опубликовать такие заявления без их серьезности.

Так это правда? Могут ли эти люди решить NP-полные задачи в P-time, используя свою модель?

np-complete open-problem Александр С Кинг
источник
1
Ответ на последний вопрос, конечно, нет. Определение P не изменилось только потому, что кто-то изобрел необычную новую модель вычислений.
Эмиль Йержабек
@ EmilJeřábek, они не просто изобрели новую вычислительную модель, они также утверждали, что она эквивалентна NP.
Александр С Кинг
3
Вы что-то путаете. Если бы они доказали, что их модель эквивалентна P, то это будет означать, что P = NP.
Сашо Николов
В реферате статьи содержится следующее утверждение: «Недавно было математически доказано, что вычислительные машины обладают той же вычислительной мощностью, что и недетерминированные машины Тьюринга». Это просто означает, что две модели способны решать одни и те же алгоритмические задачи. Это не означает, что полиномиальные временные сложности снова переводятся в полиномиальные временные сложности.
Гамов
12
См. Chat.stackexchange.com/transcript/9446/2015/12/21 , особенно scottaaronson.com/blog/?p=2212
Томас Климпел

Ответы:

9

Я чувствую, что на это достаточно ответили в комментариях, поэтому просто подведу итог:

  • Авторы не претендуют на P = NP, что является утверждением о детерминированных и недетерминированных машинах Тьюринга.

  • Авторы предлагают модель вычислений, которые, как они утверждают, показывают, эквивалентны по мощности недетерминированным машинам Тьюринга.

  • Авторы конструируют физические машины, которые реализуют эту модель вычислений для небольших входных размеров.

  • Авторы утверждают, что создание более крупных версий физически осуществимо / возможно с использованием ресурсов полиномиального размера.

  • Это последнее утверждение, которое, конечно, не доказано и на самом деле не является формальным утверждением, подразумевает, что, как правило, физически возможно решить NP-полные проблемы с ресурсами полиномиального размера.

  • Скотт Ааронсон в своем блоге объясняет, почему это последнее утверждение проблематично и почему у масштабируемости их подхода есть проблемы: http://www.scottaaronson.com/blog/?p=2212

усул
источник
Хотелось бы отметить, что на сегодняшний день (октябрь 2019 г.) ни один исследователь не воспроизводил NP-полный решатель из этой статьи 2015 года. Более того, во всех последующих последующих статьях memcomputing тех же авторов не было ни одной строки кода, которая бы помогла воспроизвести NP-полный решатель.
Г. Коэн