A Polynomial Solution for 3-SAT in the Space of Cellular Automata in the Hyperbolic Plane

Maurice Margenstern (G.I.F.M., Université de Metz, I.U.T. de Metz, Département d'Informatique, Ile du Saulcy)

Kenichi Morita (University of Hiroshima, Faculty of Engineering, Higashi-Hiroshima, Japan)

Abstract: 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.

Keywords: cellular automata, complexity theory, hyperbolic plane

Categories: F.1.1, F.1.3