A Polynomial Solution for 3-SAT in the Space of Cellular Automata in the Hyperbolic Plane
Дата
Авторы
Margenstern,Maurice
Morita,Kenichi
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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