3 ms·
chess is actually not very easy to check. chess is in exp, the class of problems requiring exponential time to solve and exponential time to check. unlike p vs
by ellis-bell 6y ago
chess is actually not very easy to check.
chess is in exp, the class of problems requiring exponential time to solve and exponential time to check. unlike p vs np we do know that exp \neq p.
- whatshisface 6y agoIt takes O(n) to check if a chess game follows the rules, and to check who wins. Same for checking a proof written in CoQ. What do you mean by "check?"