7
$\begingroup$

Recently I am reading a document [1]. In this document, Prof. Cook provides a brief proof of $\mathbf{P} \subseteq \mathbf{NP}$, which is only one sentence:

It is trivial to show that $\mathbf{P} \subseteq \mathbf{NP}$, since for each language $L$ over $\Sigma$, if $L \in \mathbf{P}$ then we can define the polynomial-time checking relation $R \subseteq \Sigma^* \cup \Sigma^*$ by $$R(w, y) \Longleftrightarrow w \in L$$ for all $w, y \in \Sigma^*$.

I know the definitions of $\mathbf{P}$ and $\mathbf{NP}$, as in [1], but I still can't understand this proof. Could any one explain the proof to me? Even one sentence is good.

By the way, I think $\Sigma^* \cup \Sigma^*$ should be $\Sigma^* \times \Sigma^*$. Am I right?

Reference

[1] S. Cook, The P versus NP problem, [Online] http://www.claymath.org/sites/default/files/pvsnp.pdf.

$\endgroup$
  • 2
    $\begingroup$ yes it should be a $\times$ $\endgroup$ – adrianN May 20 '16 at 10:11
  • 1
    $\begingroup$ For almost every equivalent definitions of $P$ and $NP$, there are one line proofs for $P \subseteq NP$. $\endgroup$ – Shreesh May 20 '16 at 13:01
  • $\begingroup$ @Shreesh Could you please tell me where can I find these one-line proofs? Thank you very much. $\endgroup$ – Wei-Cheng Liu May 23 '16 at 1:13
  • 1
    $\begingroup$ Gary & Johnson use different definition for NP, but they use simple proof (just a mention) to show that $P \subseteq NP$, basically ignore the guess string. The certificate definition is used in Arora and Barak, they also use simple proof (just a hint) for $P \subseteq NP$, which basically ignores the certificate. Hopcroft an Ullman use different definition for NP, and they ignore non-determinism to prove $P \subseteq NP$ (just a mention in the text, that it can be done). $\endgroup$ – Shreesh May 23 '16 at 17:13
12
$\begingroup$

Since L is in P, you can answer the word problem in polynomial time. To show that L is in NP as well, we need to provide a polynomial checking relation $R$ such that

$$ w\in L \Leftrightarrow \exists y.(|y|\le |w^k| \text{ and } R(w,y))$$

Now Prof. Cook says to take a very simple $R$. For every $w$ in $L$, no matter what $y\in \Sigma^*$ you take, $R(w,y)$ is true and for every $w$ not in $L$, $R(w,y)$ is false, regardless of the $y$. This is a polynomial time relation, since we can decide whether $w\in L$ or not in polynomial time (since $L \in P$), without looking at $y$ at all. And as any $y$ works, there are also some $y$ that are short enough to satisfy the length restriction in the above definition.

$\endgroup$
3
$\begingroup$

$P=\{L : L\ \text{is decided by a }\mathbf{deterministic}\text{ Turing machine in polynomial time}\}$

$NP=\{L : L\text{ is decided by a (possibly non-deterministic) Turing machine in polynomial time}\}$

With these definitions, $P\subseteq NP$ is fairly obvious.

Let's call $\widetilde{NP}=\{L : \text{There is some } R \text{ so that } L_R\in P\}$ where $R\subseteq \Sigma^*\times \Sigma'^*$ and $L_R=\{u\#v : (u,v)\in R\}$. The idea here is that $u$ is the "real" input and $v$ is some extra information to help us know why we should accept $u$. For example, if the problem is $SAT$, $u$ is the formula and $v$ can be a valuation.

  • $\widetilde{NP}\subseteq NP$ : Guess $v$ and then verify $u\#v$ it.

  • $NP\subseteq\widetilde{NP}$ : Given $u$, $v$ will be the list transitions taken in an execution accepting $u$. To verify $u\#v$, you just need to simulate the execution of the non-deterministic machine on $u$ while using $v$ to remove non-determinism.

The proof you're referring to is just saying that $P\subseteq \widetilde{NP}$ and you don't even need $v$ because there is no non-determinism to remove.

And yes, it should be $\Sigma^* \times \Sigma^*$.

$\endgroup$
  • $\begingroup$ I have read your answer, thank you very much. But I can't understand the contents "$\widetilde{NP} \subseteq NP$ ... no non-determinism to remove." Could you please explain it to me? Thanks in advance. $\endgroup$ – Wei-Cheng Liu May 26 '16 at 2:48
  • 1
    $\begingroup$ When you prove that $NP \subseteq \widetile{NP}$, you take a problem $X\in NP$ and try to prove that $X \in \widetile{NP}$. Since $X$ is in $NP$, you have a non-deterministic Turing machine $M$ that decides it in polynomial time $f(n)$ for any input of size $n$. To prove it's in $\widetile{NP}$, you need to provide a deterministic verifier. Since you know close to nothing about $X$, it seems fairly obvious that you'll have to use $M$ to construct the verifier. But $M$ is non-deterministic and you want a determnistic verifier. You you need to "remove the non-determnism". $\endgroup$ – xavierm02 May 26 '16 at 8:44
  • 1
    $\begingroup$ You do that by taking the list of transitions of the machine taken during an accepting execution as certificate. This gives you a certificate of size $P(n)$ and given the list of transition, you can simulate $M$ and just follow those transitions, so that even though $M$ is non-deterministic, you can simulate this execution in a deterministic way in polynomial time. | Now if you do the exact same thing with $P$ instead of $NP$, you don't need the certificate because $M$ is already deterministic, and so just having the input lets you infer all the transitions that were taken. $\endgroup$ – xavierm02 May 26 '16 at 8:47
  • $\begingroup$ I have read your comments carefully. Thank you very much. But there are some proper nouns I still can't understand. What is the verifier? What is the deterministic verifier? What is the certificate? Could you please explain them to me? Or could you please list some references so that I can understand these proper nouns from the references? Thanks in advance. $\endgroup$ – Wei-Cheng Liu Jun 2 '16 at 2:17

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.