4 ms·
Chess is decidable, it may be PSPACE-hard or EXPTIME-hard, but there are reductions. Entscheidungsproblem and Halt are not decidable in the general case. Whil
by nyrikki 3y ago
Chess is decidable, it may be PSPACE-hard or EXPTIME-hard, but there are reductions.
Entscheidungsproblem and Halt are not decidable in the general case.
While you have to find reductions, decidable problems having access to both yes-instances and no-instances makes it easier to find them.
- itishappy 3y agoKnowing that we don't approach either by attempting to fully solve them, does that change the architecture, or just the difficulty?