4 papers
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 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…
Perfect Information Hearthstone is PSPACE-hard
Zhujun Zhang
We consider the computational complexity of Hearthstone which is a popular online CCG (collectible card game). We reduce a PSPACE-complete problem, the partition game, to perfect i…
A Note on the Computational Complexity of Selfmate and Reflexmate Chess Problems
Zhujun Zhang
A selfmate is a Chess problem in which White, moving first, needs to force Black to checkmate within a specified number of moves. The reflexmate is a derivative of the selfmate in…