Is P = NP when solutions length is polynomially bounded by instance length? I'm currently reading the book "P, NP, and NP-Completeness" by Oded Goldreich. I'm currently reading a chapter that's concerned with the "search version" of the P-vs-NP-problem, that is if finding solutions is harder than checking the validity of solutions.

First, the book defines "polynomially bounded relations" as relations (between problem instances x and their solutions y) where there exists some polynomial p such that the length of the solution is polynomially bounded by the length of the related problem instance (that is |y| &lt;= p(|x|)).

Both the search problem as well as the checking problem are then defined on such bounded relations.

Now I wonder: Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates, which, when given an algorithm C that checks a solution for its validity in polynomial time, implies that finding a solution can also be done in polynomial time by simply checking each of the possible solutions for its validity?

This would mean that if I can efficiently check solutions of a problem for validity, then I can also efficiently find solutions to that problem. (So, basically P = NP)

Is this conclusion - when only looking at polynomially bounded relations - true? (The book of course says that it's not. If I'd need to bet I'd also bet on the book and not on me...)

If not, where is the error in my reasoning?
You ask


  Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates?


In fact, the number of binary strings of length $n^c$ is $2^{n^c}$, which is exponential in $n$.