0
$\begingroup$

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

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

I think this also has to be true in this case 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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ You are just asking if P is subset of NP. Wikipedia has answer. $\endgroup$ – rus9384 Oct 3 '17 at 10:11
  • $\begingroup$ P is a subset of NP. Which means that it has to be true. $\endgroup$ – MBD Oct 3 '17 at 10:20
  • 1
    $\begingroup$ You have answered your question. $\endgroup$ – rus9384 Oct 3 '17 at 10:22
0
$\begingroup$

"I wonder if: P is the set of languages that can be decided by a non-deterministic Turing Machine in polynomial runtime?". This is the same as asking whether $NP$ is contained in $P$.

The answer is: we don't know yet!

$NP$ is the set of languages that can be decided by a $NTM$ in polynomial time. And $P$ is the set of languages that can be decided by a $TM$ in polynomial time.

As you mentioned, clearly $P$ is contained in $NP$. But the question of whether $NP$ is contained in $P$ is still open.

| cite | improve this answer | |
$\endgroup$
  • $\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 Oct 3 '17 at 13:45
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)$.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

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