<p>It is well known that Chess is EXPTIME-Complete. </p>

<p>I am interested in the related "Helpmate" problem. Given an $N$ by $N$ chessboard, is there any sequence of at most $k$ moves that leads to Black's checkmate? To clarify, both players are cooperating to end the game in Black's checkmate.</p>

<p>I could not find any literature discussing the computational complexity of the problem, perhaps I am not searching for the right terms.</p>

CC BY-SA 3.0
2018-01-27T15:30:48.850Z
If $k$ is encoded in unary, then the Helpmate problem is in NP, and it should be NP-complete (by emulating some reachability problem).
Gamow
CC BY-SA 3.0
2018-01-27T18:15:16.783Z
A closely related question has been posed here: https://cs.stackexchange.com/questions/58156/what-complexity-class-would-this-version-of-generalized-chess-fall
Gamow
<cc.complexity-theory>
Computational Complexity of the Helpmate problem in Chess
KKOrange
# Computational Complexity of the Helpmate problem in Chess

(Asked by: username_0 on 2018-01-27)

It is well known that Chess is EXPTIME-Complete.

I am interested in the related "Helpmate" problem. Given an $N$ by $N$ chessboard, is there any sequence of at most $k$ moves that leads to Black's checkmate? To clarify, both players are cooperating to end the game in Black's checkmate.

I could not find any literature discussing the computational complexity of the problem, perhaps I am not searching for the right terms.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: If $k$ is encoded in unary, then the Helpmate problem is in NP, and it should be NP-complete (by emulating some reachability problem).  
> **username_1**: A closely related question has been posed here: https://cs.stackexchange.com/questions/58156/what-complexity-class-would-this-version-of-generalized-chess-fall  

---

## 0 answers

