An one-sentence proof of P ⊆ NP

Question

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.

Answer 1

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.

Answer 2

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