NP problems are tractable in the space of cellular automata in the hyperbolic plane

AbstractIn this paper, we define cellular automata on a grid of the hyperbolic plane that is based on the tessellation obtained from the regular pentagon with right angles. Owing to the properties of that grid, we show that 3-SAT can be solved in polynomial time in that peculiar setting; then we extend that result for any NP problem. On this ground, several directions are indicated