[Solved]: Why does the solution of an NP problem have to be polynomial size?

Problem Detail: 

I've read in "Introduction to Algorithms" (CLRS) that formal language $L$ is NP-language if and only if there is a polynomial verification algorithm $A(x, y)$ and a constant $c$ such that $$L=\{x\in\{0,1\}\mid \exists y \text{ with } |y| \leq |x|^c\text{ and } A(x, y)=1 \}\,.$$

What is the purpose of the constraint: $|y| \leq(|x|^c)$?

Asked By : Alexander_KH

Answered By : David Richerby

First, let's refresh the proof that the definition given is indeed equivalent to the standard definition of NP, i.e., the class of languages accepted by polynomial-time nondeterministic Turing machines.

Suppose $L$ is accepted by a polynomial-time Turing machine $M$. There is some $c$ such that $M$ runs in time $|x|^c$ for all inputs $x$. The verification algorithm is as follows: given $x$ and $y$, interpret $y$ as being a sequence of states of $M$ (expressed in some appropriate alphabet), and accept the pair $(x,y)$ if, and only if, $y$ describes an accepting path of $M$ on input $x$. Now, for any string $x\in L$, $M$ has an accepting path of length at most $|x|^c$, there exists a $y$, also of length at most $|x|^c$, such that $A$ accepts $(x,y)$. If $M$ rejects $x$, then there is no accepting path, so no string $y$ can describe an accepting path, so $A$ rejects $(x,y)$ for any string $y$.

Conversely, suppose that a polynomial-time algorithm $A$ exists with the properties stated in the question. We can construct a nondeterministic polynomial-time algorithm for $L$ as follows. Given input $x$, nondeterministitically "guess" (generate) a string $y$ of length at most $|x|^c$ and see if $A$ accepts $(x,y)$. If $x\in L$, then there is a string $y$ of length at most $|x|^c$ such that $A$ accepts $(x,y)$, so our machine accepts; if $x\notin L$, then no string $y$ has the desired property, so our machine rejects. This is a nondeterministic polynomial time algorithm because it does a polynomial about of guessing and a polynomial amount of simulation of $A$.

So, what goes wrong with this if we remove the condition that there exists some $y$ specifically with length at most $|x|^c$? Well, the first half of the proof still works: if $L$ is in NP then $A$ exists and, hey, it still happens to have the property that $|y|\leq |x^c|$, even though that wasn't required. However, the other half of the proof breaks. We no longer have the guarantee that it's enough to guess $|x|^c$ bits. In fact, we have no guarantee at all. We'd have to keep guessing longer and longer strings to test with $A$ and, actually, the procedure would never terminate for $x\notin L$: there's no way to tell if there really is no $y$ for which $A$ accepts $(x,y)$ or if there is such a $y$ but it's just so long that you've not seen it yet (undecidability of the halting problem).

So, without the polynomial bound on $|y|$, every NP langauge can still be expressed in this way but, unfortunately, so can all recursively enumerable languages. The polynomial bound is required to restrict the class of languages described to just NP.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29340

3.2K people like this

 Download Related Notes/Documents