HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

An one-sentence proof of P ⊆ NP

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
onesentenceproof

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#57656, answer score: 12

Revisions (0)

No revisions yet.