3
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\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$ – JMP Oct 17 '15 at 14:09
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ You said "any deterministic TM is also a non-deterministic TM (but the converse is not true)". Do we know that the converse is not true? Meaning, atleast when restricted to polynomial time, it is the $P$ vs $NP$ problem. $\endgroup$ – kishlaya May 14 '20 at 11:37
  • 1
    $\begingroup$ @kishayla Yes, the converse is not true. If P=NP there may be an equivalent deterministic TM that is only slower by a polynomial factor for each nondeterministic TM. But they are not the same machine. But deterministic Turing Machines are by definition a subset of nondeterministic ones: an NTM can have arbitrarily many transitions from each state, but a DTM has at most one. $\endgroup$ – jmite May 14 '20 at 16:19
  • $\begingroup$ Ah! I see. I completely got mistaken here. Thank you for the clarification. $\endgroup$ – kishlaya May 17 '20 at 6:33
  • 1
    $\begingroup$ I have this one related question: So if we consider the sets of languages decided by a deterministic TM and set of languages decided by a non-deterministic TM. Are those the same sets? When restricted to polynomial time, then it is the $P$ vs $NP$ problem. Am I right? $\endgroup$ – kishlaya May 17 '20 at 6:45
  • 1
    $\begingroup$ @kishlaya Right. When there's no time bound on the Turing Machines, there is a theorem that deterministic and non-deterministic machines decide the same languages. With the polynomial time bound, that's $P vs. NP$, which is still an open problem. $\endgroup$ – jmite May 17 '20 at 15:53
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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

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.