Re: Problems in NP with infinite number of possibiltiies to check?

jarfo wrote:

No.

The additional input to the P verifier (certificate or proof) is (polynomially) bounded, so you can have only a finite number of different 'certificates' to explore. In other words, the verifier can only read a finite number of bits in its time bound.

If for the P verifier time-bounded by n^k the the number of possibilities to check is bounded by 2^(n^k)


Isn't that a bound on the number of solutions with different
certificates, rather than on the size of the solution space?

.