Suppose there exist deterministic turing machine $M$ that could solve SAT in polynomial time. How can we construct a deterministic TM $N$ ,by using SAT solver $M$, that take as input a non-deterministic TM for language $L$ and output a deterministic TM for $L$.

I know we can convert NTM to TM but im looking for a way with help of a SAT solver turing machine.

  • $\begingroup$ Are you hoping for a speedup over the exponential slowdown of converting a NTM to a TM the more generic way? $\endgroup$
    – Jake
    Aug 9, 2021 at 18:37
  • $\begingroup$ Time is not important. The main problem is how can $M$ be used for conversion. I a looking for an algorithm that $M$ is used in it. $\endgroup$
    – user139795
    Aug 10, 2021 at 5:25

2 Answers 2


You can already convert a non-deterministic TM into a deterministic TM, even without a polynomial-time SAT solver. The deterministic TM will be much slower.

Having a polynomial-time SAT solver doesn't help with this process, except in very special cases, like for non-deterministic TMs that always output yes in polynomial time (which you would be able to convert to equivalent deterministic TMs that always output yes/no in polynomial time).

  • $\begingroup$ Thanks but this is not what i was looking for. $\endgroup$
    – user139795
    Aug 7, 2021 at 4:41
  • 1
    $\begingroup$ @alfred This post seems to answer the question written above. If this answer does not solve your problem, it would be useful if you tell us why. Additionally, please clarify your question by editing your question to make it more clear what you are looking for. $\endgroup$
    – Discrete lizard
    Aug 8, 2021 at 9:19
  • $\begingroup$ @ Discrete lizard thanks. i edited the question. $\endgroup$
    – user139795
    Aug 8, 2021 at 19:05

So i just add my Solution maybe somebody find it useful. We construct $N$ as fallows

N : on input T which is a turing machine  
    construct T' such that on input w : 
        it converts T,w to logical formula f as in Cook–Levin theorem 
        Run M on f and  output whatever M decides

Your Answer

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