No abstract uploaded!

No abstract uploaded!

The Hamiltonian cycle problem is an important problem in graph theory and computer science. It is a special case of the famous traveling salesman problem. A signicant amount of research has been done on the special cases of nding Hamiltonian cycles in subgraphs of triangular, square and hexagonal grids. However, there is little work on more complicated grids. In this paper, we investigate the hardness of Hamiltonian cycle problem in grid graphs of semiregular tessellations, which are tessellations formed by two or more kinds of regular polygons. There are only eight semiregular tessellations, and we prove that the Hamiltonian cycle problem in all of them are NP-complete by reducing from NP-complete problems, such as the Hamiltonian cycle problem in max degree 3 bipartite planar graphs. Knowing the NP-completeness of Hamiltonian cycle problem in semiregular grids indicates that there will not be any polynomial time algorithm that solves the Hamiltonian path problem in these tessellations if NP does not equal to P, which helps show the limits of ecient motion planning algorithms and provides new information about what makes problems computationally dicult to solve.

To study arithmetic structures of natural numbers, we introduce a notion of entropy of arithmetic functions, called anqie entropy. This entropy possesses some crucial properties common to both Shannon's and Kolmogorov's entropies. We show that all arithmetic functions with zero anqie entropy form a C*-algebra. Its maximal ideal space defines our arithmetic compactification of natural numbers, which is totally disconnected but not extremely disconnected. We also compute the $K$-groups of the space of all continuous functions on the arithmetic compactification. As an application, we show that any topological dynamical system with topological entropy $\lambda$, can be approximated by symbolic dynamical systems with entropy less than or equal to $\lambda$.

No abstract uploaded!