0
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.