[Solved]: An one-sentence proof of P ⊆ NP

Problem Detail: 

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.

Asked By : Wei-Cheng Liu

Answered By : adrianN

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.

Best Answer from StackOverflow

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