4 ms·
A simple answer to OPs question should be "Yes". Given a finite number of moves, the state space is finite and thus, e.g. using naive min-max, you can verify if
by omegalulw 5y ago
A simple answer to OPs question should be "Yes". Given a finite number of moves, the state space is finite and thus, e.g. using naive min-max, you can verify if you can force a checkmate. In practice this is infeasible for any large N as this is NP as you noted.
- kevinwang 5y agoIsn't this just an ordinary proof, not a zero knowledge proof? And why would you say this is infeasible for large n? NP doesn't mean that verification is hard, it means that verification is easy, no?