17

This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008.

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

In the author's opinion, the question P=NP is ill-posed because in the hyperbolic setting P=NP or in the notation used later in the book Ph=NPh.

I don't know enough about complexity to know what to make of this, but it sounds interesting.

So the question is basically, what do you make of it?

Do his claims make sense ?

Roy Maclean
  • 273
  • 1
  • 7

1 Answers1

39

P=NP is a well-defined mathematical question which does not depend on space-time geometry. The question "which problems can be solved by computations that are tractable in this universe?" may depend on physics, and the answer does indeed appear to change in hyperbolic space or with quantum mechanics (e.g. quantum computing). However, this doesn't affect the P=NP question.

In fact, one of the first reactions of a theoretical computer scientist would have to your reference is: "What complexity class can be computed by a cellular automaton in hyperbolic space?" If you redefine complexity classes when you change to hyperbolic space, it becomes much harder to talk about this question.

And if you look later in the book, the author defines P$_h$ as problems solvable in polynomial time on a hyperbolic cellular automaton, and proves P$_h$=PSPACE (and NP$_h$=P$_h$=PSPACE), so even the author isn't really taking complexity classes to change in hyperbolic space.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133