2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I'd appreciate help with tagging; also please comment if the question is unclear due to lacking definitions. $\endgroup$ – Daniel Jour Mar 18 '17 at 12:08
  • 1
    $\begingroup$ Hint: there are $2^n$ many binary strings of length $n$. $\endgroup$ – Yuval Filmus Mar 18 '17 at 12:23
  • $\begingroup$ @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? $\endgroup$ – Daniel Jour Mar 18 '17 at 12:29
  • $\begingroup$ You can answer your own question. $\endgroup$ – Yuval Filmus Mar 18 '17 at 12:31
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 18 '17 at 13:44
  • $\begingroup$ yes number of possible solutions candidates is $\Omega(2^n)$ $\endgroup$ – aaag Mar 18 '17 at 13:55

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.