<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-31T13:39:09.800Z
Thank you very much for this answer.
Roy Maclean
CC BY-SA 2.5
2010-10-31T16:45:45.057Z
Well quantum computing may change what's tractable, but it may not, we don't know yet...
Spudd86
CC BY-SA 2.5
2010-10-31T17:01:42.360Z
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.
Peter Shor 
CC BY-SA 2.5
2010-10-31T13:17:16.827Z
2010-10-31T13:34:04.197Z
2010-10-31T13:34:04.197Z
Peter Shor 
<p>This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008.</p>

<p><a href="http://books.google.com/books?id=eEgvfic3A4kC&amp;pg=PA125">http://books.google.com/books?id=eEgvfic3A4kC&amp;pg=PA125</a></p>

<p>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 P<sub>h</sub>=NP<sub>h</sub>.</p>

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

<p>So the question is basically, what do you make of it?</p>

<p>Do his claims make sense ?</p>

<cc.complexity-theory>
Meaning of P=NP? depends on space-time geometry ?
Roy Maclean
# Meaning of P=NP? depends on space-time geometry ?

(Asked by: username_0 on 2010-10-31)

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 ?

**Tags:** cc.complexity-theory


---

## 1 answers

### Answer by username_1 on 2010-10-31. Score: 39 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you very much for this answer.  
> **username_2**: Well quantum computing may change what's tractable, but it may not, we don't know yet...  
> **username_1**: 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.  

---

