I feel like I am really close to understanding the difference between P vs NP, and I think it comes down to this. The confusion stems from the fact that both P and NP problems are done in polynomial time, but P problems are only polynomial with a DTM (deterministic Turing machine) and NP problems are only polynomial with a NDTM (non-deterministic Turing machine).

Because of the Church-Turing thesis, we know we can construct a DTM that accepts the same problems as a NDTM. This means we can construct a DTM that solves the NP problems.

This is the big question I have: Is the reason why (we think) P != NP because this DTM will be more complex (in terms of time complexity) than the NDTM?

Of course some NP problems are P, so those done with a NDTM and DTM will both have the same complexity (in fact the DTM is also a NDTM) but what about problems that are NP-complete? Those can be done by a NDTM in polynomial time, but will the DTM for that problem always be more complex and by how much?

My understanding for that last question is that the DTM will always be more complex (if P != NP) and it will actually have an exponential time complexity and this is because the DTM will essentially be doing a breadth-first search of the configuration tree of the NDTM.

So my final question, assuming my understanding so far is correct, is why is the breadth-first search of the configuration tree going to take exponential time? e.g. if the problem was done in O(n^2) time by the NDTM, why would doing the breadth-first search for finding the solution in the configuration tree take O(a^n) (for some a > 1)?


  • $\begingroup$ SAT can be solved in polynomial time on a nondeterministic Turing machine. Try to come up with a polynomial time algorithm for SAT on a deterministic Turing machine to see what goes wrong. (You can replace SAT with an NP-complete problem of your choice.) $\endgroup$ Nov 5 '20 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.