# Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?

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?

• 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. Commented Jan 23, 2023 at 14:55
• I just mean that the TM would be executing the most efficient algorithm for solving said decision problem - apologies for the ambiguity Commented Jan 23, 2023 at 20:36

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.