NP problems are tractable in the space of cellular automata in the hyperbolic plane. (English) Zbl 0972.68119
Summary: We define cellular automata on a grid of the hyperbolic plane that is based on the tessellation obtained from the regular pentagon with right angles. Owing to the properties of that grid, we show that 3-SAT can be solved in polynomial time in that peculiar setting; then we extend that result for any NP problem. On this ground, several directions are indicated.
MSC:
| 68Q80 | Cellular automata (computational aspects) |
References:
| [1] | S. Arora, Polynomial time approximation schemes for euclidean TSP and other geometric problems, Proc. 37th IEEE FOCS, 1996.; S. Arora, Polynomial time approximation schemes for euclidean TSP and other geometric problems, Proc. 37th IEEE FOCS, 1996. |
| [2] | Carathéodory, C., (Theory of Functions of a Complex Variable, vol. II (1954), Chelsea: Chelsea New York), 177-184 · Zbl 0056.06703 |
| [3] | Garey, M. R.; Johnson, D. S., Computers and IntractabilityA Guide to the Theory of NP-completeness (1979), W.H. Freeman and Co: W.H. Freeman and Co San Francisco · Zbl 0411.68039 |
| [4] | Guggenheimer, H. W., Plane Geometry and its Groups (1967), Holden Day, Inc.: Holden Day, Inc. San Francisco · Zbl 0147.38801 |
| [5] | Gurevich, Yu., Kolmogorov machines and related issues, Bull. European Assoc. Theor. Comput. Sci., 35, 71-82 (1988) |
| [6] | Iversen, B., Hyperbolic Geometry (1992), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0766.51002 |
| [7] | Magnus, W., Noneuclidean Tessellations and their Groups (1974), Academic Press: Academic Press New York · Zbl 0293.50002 |
| [8] | Maskit, B., On Poincaré’s theorem for fundamental polygons, Adv. Math., 7, 219-230 (1971) · Zbl 0223.30008 |
| [9] | Meschkowski, H., Noneuclidean Geometry, translated by A. Shenitzer (1964), Academic Press: Academic Press New York · Zbl 0126.36804 |
| [10] | Poincaré, H., Théorie des groupes fuchsiens, Acta Mathematica, 1, 1-62 (1882) · JFM 14.0338.01 |
| [11] | Ramsay, A.; Richtmyer, R. D., Introduction to Hyperbolic Geometry (1995), Springer: Springer Berlin · Zbl 0816.51002 |
| [12] | Robinson, R. M., Undecidable tiling problems in the hyperbolic plane, Invent. Math., 44, 259-264 (1978) · Zbl 0354.50006 |
| [13] | L. Trevisan, On the approximability of the multidimensional euclidean, TSP, Tech. Report SI/RR/96/15, University of Roma 1, 1996.; L. Trevisan, On the approximability of the multidimensional euclidean, TSP, Tech. Report SI/RR/96/15, University of Roma 1, 1996. |
| [14] | Wagner, K.; Wechsung, G., Computational Complexity (1986), VEB Deutscher Verlag der Wissenschaften: VEB Deutscher Verlag der Wissenschaften Berlin · Zbl 0651.00005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
