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


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 ?


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.

  • 1
    $\begingroup$ Thank you very much for this answer. $\endgroup$ – Roy Maclean Oct 31 '10 at 13:39
  • $\begingroup$ Well quantum computing may change what's tractable, but it may not, we don't know yet... $\endgroup$ – Spudd86 Oct 31 '10 at 16:45
  • 7
    $\begingroup$ That's why I said "appears to change" rather than "changes". The same is true with hyperbolic space; we don't know that P$\neq$PSPACE, although that's less uncertain than P$\neq$BQP. $\endgroup$ – Peter Shor Oct 31 '10 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.