Are problems with an arbitrarily large search space in NP?

Question

Let's say I have a problem with some input x. Each input x induces some arbitrarily large (but finite) search space. To make this more concrete, let's say a set of size proportional to 2^2^2^|x|. For each element in this search space we can check whether or not it meets a certain property P in polynomial time. I want an input x to be a 'yes' instance of my problem iff at least one element of the search space meets property P.

Are all problems of this form in NP, no matter how the search space scales with regards to the input? Naïvely I would say a Nondeterministic Turing Machine could just guess the element of the search space that holds the property, but this assumes they can branch arbitrarily, and that we don't have to have a fixed NTM for all input sizes.

I think an answer to How a NTM guessing depends on the input? would also basically answer my question, but it didn't really get an answer.

Answer 1

let's say a set of size proportional to 2^2^2^|x|. For each element in this search space we can check whether or not it meets a certain property P in polynomial time.

The time must be polynomial with respect to the problem instance, not the solution in the search space.

NP problems are those with polynomial-time verifiers for certificates ("solutions") whose size is polynomial with respect to the input, so they can only describe search spaces of exponential size $2^{\mathrm{poly}(\mathrm{size}(\mathrm{input}))}$.

Said another way, NP languages are recognized by polynomial-time nondeterministic Turing machines. They can only make a polynomial amount of "0 or 1" guesses.