Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 5 / Issue 9

available in:   PDF (184 kB) PS (65 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-005-09-0563


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