Proving that $P \subseteq NP,$ formally and using Turing Machines.

44 Views Asked by At

My question urges on proving that $P \subseteq NP.$ The definitions I am using follow below:

Definition. We define the set of languages $DTime$ as $$ DTime(t(n)) = \{ L \colon \text{there is a deterministic decider of $L$ that runs in $\mathcal O(t(n))$}\},$$ where $t \colon \mathbb N_0 \to \mathbb N_0$. From here, we defined the class $P$ as $$ P = \bigcup_{k \geqslant 0} DTime(n^k) $$

Definition. We define the set of languages $NTime$ as $$ NTime(t(n)) = \{ L \colon \text{there is a non-deterministic decider of $L$ that runs in $\mathcal O(t(n))$}\},$$ where $t \colon \mathbb N_0 \to \mathbb N_0.$ From here, we define the class $NP$ as $$ NP = \bigcup_{k \geqslant 0} NTime(n^k).$$

The main objetive. I am looking forward to show that $P \subseteq NP.$

My attempt. Consider an arbitrary language in the class $P$. Then, we can guarantee that there is a deterministic decider of $L$ that runs in $\mathcal O(n^k),$ for some $k \in \mathbb N_0.$ To prove that this same language is in $NP$, one should show that there exists a non-deterministic decider of $L$ that runs in $\mathcal O(n^p),$ for some non-negative integer $p$.

Let $M = (Q,\Sigma,\tau, \delta,s,F)$ be the deterministic decider of $L$ that we know exists and let $M_1 = (Q,\Sigma,\tau,\delta_1,s,F)$ be a non-deterministic decider such that it has the exact same states as $M$, and so on... . We define its transition function as follows: for every $q \in Q, a \in \tau$ such that $\delta(q,a)$ is defined:

$$ \delta_1(q,a) = \{ \delta(q,a) \}.$$

Obviously, $\mathcal L(M) = \mathcal L(M_1)$ and they also run in the same time.

My doubts. I am having a hard time proving (FORMALLY) that $\mathcal L(M) = \mathcal L(M_1)$ and that they run in the same time, altought it is clear in my intuition.