Significado de P = NP? depende da geometria espaço-tempo?

16

Esta pergunta é sobre a página 125 do livro "Autômatos celulares em espaços hiperbólicos: volume 2" Por Maurice Margenstern, Publisher Archives contemporaines, 2008.

http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125

Na opinião do autor, a questão P = NP está mal colocada, porque no ambiente hiperbólico P = NP ou na notação usada posteriormente no livro P h = NP h .

Não sei o suficiente sobre complexidade para saber o que fazer com isso, mas parece interessante.

Então a questão é basicamente, o que você acha disso?

Suas reivindicações fazem sentido?

Roy Maclean
fonte

Respostas:

38

P = NP é uma questão matemática bem definida que não depende da geometria espaço-temporal. A questão "que problemas podem ser resolvidos por cálculos tratáveis ​​neste universo?" pode depender da física, e a resposta realmente parece mudar no espaço hiperbólico ou com a mecânica quântica (por exemplo, computação quântica). No entanto, isso não afeta a questão P = NP.

De fato, uma das primeiras reações de um cientista da computação teórico a sua referência é: "Que classe de complexidade pode ser computada por um autômato celular no espaço hiperbólico?" Se você redefinir as classes de complexidade quando muda para o espaço hiperbólico, fica muito mais difícil falar sobre essa questão.

hhhh

Peter Shor
fonte
11
Muito obrigado por esta resposta.
Roy Maclean
Bem, a computação quântica pode mudar o que é tratável, mas talvez não, ainda não sabemos ...
Spudd86
7