Memcomputing realmente resolve um problema de NP-completo?

9

Me deparei com um artigo publicado na Science "Memcomputando problemas completos de NP em tempo polinomial usando recursos polinomiais e estados coletivos" , o que faz algumas afirmações bastante surpreendentes.

Memcomputing é um novo paradigma de computação não-Turing que usa células de memória em interação (memprocessors para abreviar) para armazenar e processar informações na mesma plataforma física. Recentemente, foi comprovado matematicamente que as máquinas de memcomputação têm o mesmo poder computacional das máquinas de Turing não determinísticas . Portanto, eles podem resolver problemas de NP-completos em tempo polinomial e, usando a arquitetura apropriada, com recursos que crescem polinomialmente apenas com o tamanho da entrada.

(Mina itálica).

Eu descartaria isso de imediato por não ser sério, dada a natureza forte das alegações, se não fosse pelo fato de que isso foi publicado na Science, e que o material relacionado por alguns dos autores foi publicado na Nature Physics , em um periódico do IEEE e no Physics Review E , todos eles são publicações respeitáveis ​​e revisadas por pares que não permitiriam que tais alegações fossem publicadas sem que fossem sérias.

Então é verdade? Essas pessoas podem resolver problemas de NP-completos no tempo P usando seu modelo?

np-complete open-problem Alexander S King
fonte
11
A resposta para a última pergunta é obviamente não. A definição de P não mudou apenas porque alguém inventou um novo modelo de computação sofisticado.
Emil Jerabek
@ EmilJeřábek eles não apenas inventaram um novo modelo de computação, mas também afirmaram que é equivalente a NP.
Alexander S King
3
Você está misturando algo. Se eles tivessem provado que seu modelo é equivalente a P, isso implicaria que P = NP.
Sasho Nikolov
O resumo do artigo contém a afirmação: "Foi recentemente comprovado matematicamente que as máquinas de memcomputação têm o mesmo poder computacional das máquinas de Turing não determinísticas". Isso significa apenas que os dois modelos são capazes de resolver os mesmos problemas algorítmicos. Não significa que as complexidades do tempo polinomial se convertam novamente em complexidades do tempo polinomial.
Gamow
12
Consulte chat.stackexchange.com/transcript/9446/2015/12/21 , especialmente scottaaronson.com/blog/?p=2212
Thomas Klimpel

Respostas:

9

Eu sinto que isso foi respondido suficientemente nos comentários, para resumir tudo:

  • Os autores não reivindicam P = NP, que é uma afirmação sobre máquinas de Turing determinísticas e não determinísticas.

  • Os autores propõem um modelo de computação que eles alegam mostrar é equivalente em potência às máquinas de Turing não determinísticas.

  • Os autores constroem máquinas físicas que implementam esse modelo de computação para pequenos tamanhos de entrada.

  • Os autores argumentam que a criação de versões maiores é fisicamente realizável / possível com recursos de tamanho polinomial.

  • Essa última afirmação, que obviamente não é comprovada e não é realmente uma afirmação formal, implicaria que geralmente é fisicamente possível resolver problemas completos de NP com recursos de tamanho polinomial.

  • Scott Aaronson em uma postagem no blog explica por que essa última afirmação é problemática e por que a escalabilidade de sua abordagem tem problemas: http://www.scottaaronson.com/blog/?p=2212

usul
fonte
Gostaria de observar que, até hoje (outubro de 2019), nenhum pesquisador reproduziu o solucionador NP-complete deste artigo de 2015. Além disso, em todos os artigos subsequentes relacionados aos mesmos, dos mesmos autores, não havia uma única linha de código que ajudasse a reproduzir o solucionador NP-complete.
G. Cohen