1.2k citations
- Southwest UniversityCN6 papers
- Vanderbilt UniversityUS5 papers
- Hong Kong Polytechnic UniversityHK4 papers
- Sun Yat-sen UniversityCN4 papers
- Chinese Academy of SciencesCN3 papers
- Chinese University of Hong KongHK2 papers
- Guangdong Polytechnic Normal UniversityCN2 papers
- Guilin University of Electronic TechnologyCN2 papers
- Hong Kong University of Science and TechnologyHK2 papers
- Hubei University for NationalitiesCN2 papers
- Shanghai Jiao Tong UniversityCN2 papers
- The University of MelbourneAU2 papers
6 papers · 1 filter
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…
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…
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…
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.