0
$\begingroup$

Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when being solved optimally on a DTM. Would that problem be in NP, or is solution decidability on both NDTMs and DTMs a requirement?

$\endgroup$
2
  • 1
    $\begingroup$ What do you mean by solved optimally? Also, every non-deterministic TM can be converted to a deterministic TM so I don't see how a decision problem have a non-deterministic decider but have no determinisitc decider. $\endgroup$
    – Russel
    Jan 23, 2023 at 14:55
  • $\begingroup$ I just mean that the TM would be executing the most efficient algorithm for solving said decision problem - apologies for the ambiguity $\endgroup$
    – J Jackson
    Jan 23, 2023 at 20:36

1 Answer 1

1
$\begingroup$

As DTMs and NDTMs are equivalent, every problem that can be decided by a NDTM can also be decided by a DTM.

Heres a informal explanation for NP: A deterministic turing machine can run a nonterministic program (in NP) by attempting all of the possible paths of a nondeterministic turing machine successively either until it reaches an accepting state or has found every path to be denying. If the NDTM decides the problem to be true, there must be a path of length $O(n^k)$ to an accepting state. Otherwise, every path must end in $O(n^k)$ steps. The number of possible branches at each step is limited by the alphabet size which I'll call $q$. Therefore, there are at most $q^{O(n^k)}$ possible paths if the NDTM creates q branches at each of the $O(n^k)$ steps. This is a finite number which is why all the paths can be attempted by a DTM in finite number of steps. Therefore, a decision problem which can be decided on a NDTM can also be decided on a DTM.

$\endgroup$
2
  • $\begingroup$ but at with what run-time? seems like the OP asks more about the trade-off between complete decidability and approximating a solution quickly $\endgroup$
    – nir shahar
    Jan 23, 2023 at 20:41
  • $\begingroup$ @nirshahar no, they did not say anything about the speed of solving the problem on a DTM $\endgroup$
    – user253751
    Feb 3, 2023 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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