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

Corresponding author: Maurice Margenstern ( margens@iut.univ-metz.fr )

© Maurice Margenstern, Kenichi Morita.
This article is freely available under the J.UCS Open Content License.
Citation: Margenstern M, Morita K (1999) A Polynomial Solution for 3-SAT in the Space of Cellular Automata in the Hyperbolic Plane. JUCS - Journal of Universal Computer Science 5(9): 563-573. https://doi.org/10.3217/jucs-005-09-0563
Open Access
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, hyperbolic plane, complexity theory