# 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| <= 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?

• I'd appreciate help with tagging; also please comment if the question is unclear due to lacking definitions. – Daniel Jour Mar 18 '17 at 12:08
• Hint: there are $2^n$ many binary strings of length $n$. – Yuval Filmus Mar 18 '17 at 12:23
• @YuvalFilmus oh my ... I definitely need more sleep. That's actually pretty obvious then ... Do you want to make a short answer out of that comment or shall I just delete the question? – Daniel Jour Mar 18 '17 at 12:29
• You can answer your own question. – Yuval Filmus Mar 18 '17 at 12:31

In fact, the number of binary strings of length $n^c$ is $2^{n^c}$, which is exponential in $n$.
Consider a 3-SAT formula over $n$ variables and you can see that number of possible solution candidates is $\Omega(2^n)$, where as the size of each solution is polynomially bounded in the input size.
• You want to say that the number of potential assignments is $\Omega(2^n)$ or $\Theta(2^n)$. An upper bound doesn't help here. – Yuval Filmus Mar 18 '17 at 13:44
• yes number of possible solutions candidates is $\Omega(2^n)$ – aaag Mar 18 '17 at 13:55