I am trying to understanding this. If a problem has exponential amount of candidate solutions, such as 2^2^n. Is this decidable?To my understanding, as long as its' verfiable, no matter how big the solutions there are, it's.decidable. Thanks for clarity
Decidablity with exponential number of solution
undecidability
If a problem has a finite number of possible solutions, then you can enumerate all the potential solutions, and if one of them is correct, halt. Otherwise, halt and reject after checking the last solution.It does not matter how long this process takes, it may be exponential, or superexponential as in your example of $2^{2^n}$, the only thing that matters is that there is a way to enumerate all candidate solutions.