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 $$ win 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 $yin 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 $win 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
