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$

closed as unclear what you're asking by fade2black, Luke Mathieson, David Richerby, Evil, Rick Decker Oct 3 '17 at 19:53

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.