patternMinor
Proof that $P\subseteq NP$ without nondeterministic TM
Viewed 0 times
withoutsubseteqthatnondeterministicproof
Problem
I know the proof that using nondeterministic TM, but as I understood there is another proof without nondeterministic TM.
If you answer please write with as much details as you can.
If you answer please write with as much details as you can.
Solution
The first definition you are referring to is probably the one that defines $\mathsf{NP}$ as the set of problems $\Pi$ for which there exist a non-deterministic poly-time Turing machine that decides $\Pi$.
Since any problem $\Pi \in \mathsf{P}$ can be decided by a deterministic poly-time Turing machine $T$, and $T$ itself is also a non-deterministic Turing machine, it follows that $\Pi \in \mathsf{NP}$, i.e., $\mathsf{P} \subseteq \mathsf{NP}$.
However $\mathsf{NP}$ can be equivalently defined as the set of decision problems $\Pi$ for which there exists a poly-time verifier (a Turing machine) $V$ and a polynomial $p$ such that if $x \in \{0,1\}^$ is an instance of $\Pi$, then there exists a certificate $c \in \{0,1\}^$ of length $|c| \le p(|x|)$ such that $V(x,c)$ accepts if and only if $x$ is a yes-instance for $\Pi$.
Using this definition every problem $\Pi \in \mathsf{P}$ is also in $\mathsf{NP}$, since it suffices to choose $p(|x|)=0$, $c(x)=\varepsilon$ (where $\varepsilon$ denotes the empty word), and $V(x, c)$ as the Turing machine that simulates any poly-time decider $T$ for $\Pi$ and accepts iff $T(x)$ accepts.
Since any problem $\Pi \in \mathsf{P}$ can be decided by a deterministic poly-time Turing machine $T$, and $T$ itself is also a non-deterministic Turing machine, it follows that $\Pi \in \mathsf{NP}$, i.e., $\mathsf{P} \subseteq \mathsf{NP}$.
However $\mathsf{NP}$ can be equivalently defined as the set of decision problems $\Pi$ for which there exists a poly-time verifier (a Turing machine) $V$ and a polynomial $p$ such that if $x \in \{0,1\}^$ is an instance of $\Pi$, then there exists a certificate $c \in \{0,1\}^$ of length $|c| \le p(|x|)$ such that $V(x,c)$ accepts if and only if $x$ is a yes-instance for $\Pi$.
Using this definition every problem $\Pi \in \mathsf{P}$ is also in $\mathsf{NP}$, since it suffices to choose $p(|x|)=0$, $c(x)=\varepsilon$ (where $\varepsilon$ denotes the empty word), and $V(x, c)$ as the Turing machine that simulates any poly-time decider $T$ for $\Pi$ and accepts iff $T(x)$ accepts.
Context
StackExchange Computer Science Q#134329, answer score: 7
Revisions (0)
No revisions yet.