Does P = NP in Cellular Automata of Hyperbolic Spaces?

Question

I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP according to these books/papers?

Some excerpts from the paper:

It is well known that if we have binary trees at our disposal “for free”, it is possible to solve NP-problems in polynomial time, see [14, 5]. However, it is not immediate to implement binary tree algorithms in the pentagrid, and the goal of this section is to indicate how one can proceed.

From my understanding, the P = NP problem is looking for polynomial-time algorithms to solve complicated problems. From my cursory glance through the books and papers, it seems to suggest that he has solved the problem. What am I missing?

Here is another paper, titled In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time: Towards Matiyasevich's Dream.

Answer 1

The P vs. NP problem is a question about Turing machines $T$, because the complexity classes P and NP are defined in terms of these theoretical machines. Let's call these classes $P_T$ and $NP_T$ from now on. The paper introduces a new theoretical computation machine $H$ that has associated classes $P_H$ (runs in polynomial time on the hyperbolic cellular automaton) and $NP_H$ (runs in non-deterministic polynomial time on the hyperbolic cellular automaton).

The first step in this paper is a proof that the 3SAT problem, a well known $NP_T$-complete problem, can be solved in polynomial time on this machine, i.e. this problem lies in $P_H$. Next, they show any polynomial time reduction on a Turing machine can be performed in polynomial time on their hyperbolic automaton. Since 3SAT is $NP_T$-complete, any $NP_T$ instance can be reduced to a 3SAT instance in polynomial time (on $T$ by definition, so also on $H$ by their lemma) and then be solved by solving 3SAT in poly-time, both on the hyperbolic automaton. In other words, the main result of this paper (Theorem 1) can be written as $NP_T \subseteq P_H$ in our notation. This does not give a solution to the P vs. NP problem, because that would need to relate the classes $NP_T$ and $P_T$.

Note that the authors include some remarks on the P vs. NP problem in section 4.2, where they claim their result is evidence for P$\neq$NP (!):

A third direction consists of the new light shed on the P=NP question in the ordinary settings. As the hyperbolic space has properties which are very different from the properties of the euclidean space, in particular, it has many more directions, would not that be a hint favorable to prove that P$\neq$NP in euclidean conditions? It seems that for the last ten years the works in the field of complexity incline people to believe more in P$\neq$NP. Apparently, the present result also belongs to that trend.