2 citations · 4 across the 7 of their papers we have counts for
7 papers
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…
A Note on Computational Complexity of Kill-all Go
Zhujun Zhang
Kill-all Go is a variant of Go in which Black tries to capture all white stones, while White tries to survive. We consider computational complexity of Kill-all Go with two rulesets…
A Note on Computational Complexity of Dou Shou Qi
Zhujun Zhang
Dou Shou Qi is a Chinese strategy board game for two players. We use a EXPTIME-hardness framework to analyse computational complexity of the game. We construct all gadgets of the h…
A Note on Hardness Frameworks and Computational Complexity of Xiangqi and Janggi
Zhujun Zhang
We review NP-hardness framework and PSPACE-hardness framework for a type of 2D platform games. We introduce a EXPTIME-hardness framework by defining some new gadgets. We use these…
A Note on Counting Dependency Trees
Zhujun Zhang
We apply symbolic method to deduce functional equation which generating function of counting sequence of dependency trees must satisfy. Then we use Lagrange inversion theorem to ob…
Complexity Analysis of 2-Heterogeneous Minimum Spanning Forest Problem
Zhujun Zhang, Qiang Sun
For complexity of the heterogeneous minimum spanning forest problem has not been determined, we reduce 3-SAT which is NP-complete to 2-heterogeneous minimum spanning forest problem…