JUCS - Journal of Universal Computer Science 5(9): 563-573, doi: 10.3217/jucs-005-09-0563
A Polynomial Solution for 3-SAT in the Space of Cellular Automata in the Hyperbolic Plane
expand article infoMaurice Margenstern, Kenichi Morita§
‡ G.I.F.M., Université de Metz, I.U.T. de Metz, Département d'Informatique, Ile du Saulcy§ University of Hiroshima, Faculty of Engineering, Higashi-Hiroshima, Japan
Open Access
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.
cellular automata, hyperbolic plane, complexity theory