3 ms·
For problems in NP (i.e. for which a solution can be verified in polynomial time), we can construct a Zero Knowledge Proof by reducing it to 3SAT, then construc
by aan1092j 5y ago
For problems in NP (i.e. for which a solution can be verified in polynomial time), we can construct a Zero Knowledge Proof by reducing it to 3SAT, then constructing a PCP (Probabilistically checkable proof).
T̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶o̶f̶ ̶d̶e̶t̶e̶r̶m̶i̶n̶i̶n̶g̶ ̶w̶h̶e̶t̶h̶e̶r̶ ̶y̶o̶u̶ ̶c̶a̶n̶ ̶f̶o̶r̶c̶e̶ ̶a̶ ̶c̶h̶e̶c̶k̶m̶a̶t̶e̶ ̶i̶n̶ ̶N̶ ̶m̶o̶v̶e̶s̶ ̶i̶s̶ ̶i̶n̶ ̶N̶P̶,̶ ̶s̶i̶n̶c̶e̶ ̶g̶i̶v̶e̶n̶ ̶a̶ ̶c̶a̶n̶d̶i̶d̶a̶t̶e̶ ̶s̶e̶t̶ ̶o̶f̶ ̶m̶o̶v̶e̶s̶,̶ ̶i̶t̶ ̶c̶a̶n̶ ̶b̶e̶ ̶v̶e̶r̶i̶f̶i̶e̶d̶ ̶i̶n̶ ̶p̶o̶l̶y̶n̶o̶m̶i̶a̶l̶ ̶t̶i̶m̶e̶.̶
The main challenge is the time taken to construct the proof
https://en.wikipedia.org/wiki/PCP_theorem https://en.wikipedia.org/wiki/PCP_theorem
This is where zkSNARKS help since they generate a non-interactive + succinct proof.
- omegalulw 5y agoA 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?
- kevinwang 5y agoHow do you verify a checkmate in polytime? I'd think a candidate sequence of p1,p2 moves isn't a certificate, since it says nothing about whether the losing player still gets checkmated if they make some different moves.
- Kranar 5y agoGiving a candidate set of moves that results in a checkmate does not prove that said checkmate was forced. I can provide a candidate set of moves that results in a checkmate after 3 moves (the classic Blitzkrieg), and certainly you can verify that in polynomial time, but that does not mean that it's possible to force a checkmate in 3 moves. To the best that anyone knows, for a generalized chess board of size WxW, to demonstrate that a checkmate can be forced in at most N moves, you'd need a candidate set of almost every possible sequence of N moves. You can prune some sequences, but not enough to bring the size of the candidate set down to something that can be verified in polynomial time. Chess, depending on how you generalize it, belongs to EXPTIME.
- aan1092j 5y agoAh my bad. I wrote hastily and did not consider the full implication of the word `forced`, i.e. it would involve proving the opponent has no winning options.
- red_trumpet 5y agoWhere "winning" means "surviving for N+1 moves".
- chaboud 5y agoMate can be forced in N moves. This generally requires involvement of the king (e.g., check, no other pieces, guarding of the king) such that the only legal moves remaining are dictated by the positioning of the attacker.
- SilasX 5y agoGood catch, I was scratching my head at the parent comment since I was pretty sure chess isn't in NP, so thanks for confirming and explaining why it's not.