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.