A Polynomial Solution for 3-SAT in the Space of Cellular Automata in the Hyperbolic Plane
Kenichi Morita, Maurice Margenstern · Zenodo (CERN European Organization for Nuclear Research) · 2020
In this paper, we define cellular automata on a grid of the hyperbolic plane, based on the tessellation obtained from the regular pentagon with right angles. Taking advantage of the properties of that grid, we show that 3-SAT can be solved in polynomial time in that setting, and then we extend that result for any NP problem. Several directions starting from that result are indicated.