3 citations · 4 across the 13 of their papers we have counts for
13 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 with Three Tiles
Chan Yang, Zhujun Zhang
Is there a fixed dimension such that translational tiling of with a monotile is undecidable? Several recent results support a positive answer to this question. G…
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…
Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
Chao Yang, Zhujun Zhang
This paper focuses on the undecidability of translational tiling of -dimensional space with a set of tiles. It is known that tiling with transl…
NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
Chao Yang, Zhujun Zhang
The computational complexity of tiling finite simply connected regions with a fixed set of tiles is studied in this paper. We show that the problem of tiling simply connected regio…
Undecidability of tiling the plane with a fixed number of Wang bars
Chao Yang, Zhujun Zhang
To study the fixed parameter undecidability of tiling problem for a set of Wang tiles, Jeandel and Rolin show that the tiling problem for a set of 44 Wang bars is undecidable. In t…
A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of polyominoes
Chao Yang, Zhujun Zhang
We give a proof of Ollinger's conjecture that the problem of tiling the plane with translated copies of a set of polyominoes is undecidable. The techniques employed in our proo…
Atropos-k is PSPACE-complete
Chao Yang, Zhujun Zhang
Burke and Teng introduced a two-player combinatorial game Atropos based on Sperner's lemma, and showed that deciding whether one has a winning strategy for Atropos is PSPACE-comple…
Friends-and-strangers is PSPACE-complete
Chao Yang, Zhujun Zhang
In this paper, we show that the friends-and-strangers problem is PSPACE-complete by reduction from the Ncl (non-deterministic constraint logic) problem.