2
$\begingroup$

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?

$\endgroup$
0

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – rus9384
    Commented Oct 3, 2017 at 13:45
  • $\begingroup$ His question is that. Perhaps it wasn't written clearly enough by the asker. $\endgroup$ Commented Feb 18 at 15:01
  • $\begingroup$ 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. $\endgroup$ Commented Feb 18 at 15:17
  • $\begingroup$ @rus9384 most answers interpret it as P vs NP, and my previous comment pinpoints OP's source of confusion. $\endgroup$ Commented Feb 18 at 15:21
  • $\begingroup$ 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?" $\endgroup$ Commented Feb 18 at 15:37
1
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.