6 papers
King Chasing Problem in Chinese Chess is NP-hard
Chao Li, Zhujun Zhang, Chao Yang
We prove that king chasing problem in Chinese Chess is NP-hard when generalized to boards. `King chasing' is a frequently-used strategy in Chinese Chess, which means th…
On the Undecidability of Tiling the -dimensional Space with a Set of Polycubes
Chao Yang, Zhujun Zhang
Translational tiling problems are among the most fundamental and representative undecidable problems in all fields of mathematics. Greenfeld and Tao obtained two remarkable results…
Undecidability of Translational Tiling of the Plane with Four Tiles
Chao Yang, Zhujun Zhang
The translational tiling problem, dated back to Wang's domino problem in the 1960s, is one of the most representative undecidable problems in the field of discrete geometry and com…
Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
Chao Yang, Zhujun Zhang
The first undecidability result on the tiling is the undecidability of translational tiling of the plane with Wang tiles, where there is an additional color matching requirement. L…
Translational Aperiodic Sets of 7 Polyominoes
Chao Yang, Zhujun Zhang
Recently, two extraordinary results on aperiodic monotiles have been obtained in two different settings. One is a family of aperiodic monotiles in the plane discovered by Smith, My…
Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
Chao Yang, Zhujun Zhang
Recently, Greenfeld and Tao disprove the conjecture that translational tilings of a single tile can always be periodic [Ann. Math. 200(2024), 301-363]. In another paper [to appear…