The Clay paper gives a short proof on this in page 2: http://www.claymath.org/sites/default/files/pvsnp.pdf
However,
Where does it come from that these are inclusive sets and not separate?
Or that $|P| ≤ |NP|$?
2
$\begingroup$
$\endgroup$
-
$\begingroup$ What do you mean by "inclusive sets"? $\endgroup$ – user12859 Sep 18 '15 at 13:57
-
$\begingroup$ @RickyDemer $P \subseteq NP$ requires that P is contained in (included in) NP. But I'm not sure why P is contained in NP (or why P and NP aren't separate sets, not sharing any elements or sharing only few). $\endgroup$ – mavavilj Sep 18 '15 at 13:59
-
1$\begingroup$ Can you think of a polynomial verification algorithm for $L\in P$, or in the words of the paper, a polynomial-time checking relation for $L$, that is $R\subseteq \Sigma^*\times\Sigma^* \; s.t. \; w\in L \iff \exists y\in \Sigma^{|w|^k}\; R(w,y)$. In any case, i personally wouldn't advise a first encounter with the problem using the clay institute problem statement paper. $\endgroup$ – Ariel Sep 18 '15 at 14:12
-
1$\begingroup$ This is mostly by definition; read up on the basics! See also here regarding that unfortunate misconception you state at the end. $\endgroup$ – Raphael♦ Sep 18 '15 at 17:49
-
$\begingroup$ NP is EVERY problem, P is some problems $\endgroup$ – JonMark Perry Oct 17 '15 at 14:09
5
$\begingroup$
$\endgroup$
One definition of NP is "the set of languages accepted by non-deterministic Turing Machines in polynomial time."
There's a trivial transformation that lets us convert any deterministic Turing Machine into a non-deterministic one, which will have the exact same running time. Basically, you just take the same deterministic TM, rename it as non-deterministic, and don't use any non-determinism.
In short, any deterministic TM is also a non-deterministic TM (but the converse is not true).
So, suppose there's a language $L$. If we can accept $L$ in polynomial time with a deterministic TM, then we just make the trivial non-deterministic TM which runs identically, and we can now accept $L$ in polynomial time with a non-deterministic Turing Machine.
We know that $|P| = |NP|$ because both sets are infinite and countable. There are countably many Turing Machines, since each Turing Machine can be represented as an integer. There is at least one Turing Machine for each language in $NP$, and likewise, at least one Turing Machine for each language in $P$. Since both of these sets are infinite, they must be infinite countable.
3
$\begingroup$
$\endgroup$
P is the set of languages $L$ for which there exists a polytime function $f$ such that $$ x \in L \Longleftrightarrow f(x)=Yes. $$ NP is the set of languages $L$ for which there exists a polytime function $f$ and an integer $k$ such that $$ x \in L \Longleftrightarrow f(x,y)=Yes\text{ for some $y$ of length $|y| \leq k|x|^k$}. $$ (Here $|x|$ is the length of $x$.)
Hopefully you can now show that P$\subseteq$NP on your own.
answered Sep 18 '15 at 15:05
-
$\begingroup$ Does the Clay paper confuse this by referring to the $R(w,y)$ checking relation? $\endgroup$ – mavavilj Sep 18 '15 at 15:08
-
$\begingroup$ No, there are multiple equivalent ways of stating the definitions of P and NP. $\endgroup$ – Yuval Filmus Sep 18 '15 at 15:09
-
$\begingroup$ I was interested in the Clay paper one. Unless this is (as it seems) a simpler way to state the same thing. $\endgroup$ – mavavilj Sep 18 '15 at 15:10
-
$\begingroup$ The definitions are very similar. The terminology is a tiny bit different, that's all. I suggest you follow Ariel's suggestion and take a basic course in complexity theory. The Clay document is supposed to be the "official" description of the problem, not a source for students. $\endgroup$ – Yuval Filmus Sep 18 '15 at 15:14
