# Non-deterministic TM and problems in class P [closed]

Definition: $$\text{P}$$ is the set of languages that can be decided by a deterministic Turing Machine in polynomial time.

I wonder if $$\text{P}$$ equals to the set of languages that can be decided by a non-deterministic Turing Machine in polynomial time?

I think this has to be true because a non-deterministic Turing Machine can also decide all problems which can be decided by a deterministic Turing Machine. Because of the fact that we have here a language in P this NTM also decides it in P.

Am I right or am I wrong?

I wonder if $$\text{P}$$ is the set of languages that can be decided by a non-deterministic Turing machine in polynomial time?

This is the same as asking whether $$\text{P} = \text{NP}$$, where $$\text{NP}$$ is the set of languages that can be decided by nondeterminsitic Turing machines in polynomial time. The question of whether $$\text{P} =\text{NP}$$ is an open problem. So we don't know the answer yet.

I think this has to be true because a non-deterministic Turing Machine can also decide all problems which can be decided by a deterministic Turing Machine.

The fact that nondeterministic Turing machines can simulate deterministic Turing machines without any time blowup (simply by not using nondeterminisim) is straight-forward and only shows that $$\text{P} \subseteq \text{NP}$$, the mysterious open containment is the other one: we don't know yet whether deterministic Turing machines can simulate nondeterministic Turing machines with at most polynomial blow-up.

• You have messed everything: P vs. NP asks if every problem in NP can be decided by deterministic Turing machine in polynomial time. His question is not that. Commented Oct 3, 2017 at 13:45
• His question is that. Perhaps it wasn't written clearly enough by the asker. Commented Feb 18 at 15:01
• I think the question is whether the notion that "a non-deterministic Turing Machine can also decide all problems which can be decided by a deterministic Turing Machine" is saying P=NP is correct. It is not correct, answered in passing with "This shows that P⊆NP". Perhaps, you can elaborate this a bit. Commented Feb 18 at 15:17
• @rus9384 most answers interpret it as P vs NP, and my previous comment pinpoints OP's source of confusion. Commented Feb 18 at 15:21
• It is indeed was not written clearly, but I think it asks whether P=NP: "I wonder if P is the set of languages that can be decided by a non-deterministic Turing machine in polynomial time?" Commented Feb 18 at 15:37

The class $P$ is a subset of $NP$. For an $NP$ algorithm to simulate $P$ in polynomial time, it does not even need to use nondeterminism, since a single branch can solve the $P$ problem.

It could be a bit confusing though when textbooks say that an $NP$ algorithm works in 'polynomial time'. But this refers to the amount of time it takes for a single branch to compute. But taken as a whole, $NP= \cup NTIME(n^k)$, while $P= \cup DTIME(n^k)$.

Every problem of class P is also of class NP. NP means we can verify a solution to a problem in polynomial time. If a problem is in the P class, one method of verifying the solution would be to find the solution in polynomial time. Thus, the P problem is NP class.