enter image description here

( Source: Introduction to the theory of computation, Michael Sipser, 3rd edition )

I know the computation-time of a non-deterministic Turing machine ( NTM ) which is a decider is defined to be the depth of its configuration tree.

In the above example of showing that $ HAMPATH \in NP $ , where it's highlighted in red - I understand that choosing a specific list of nodes costs polynomial time which is the depth of the configuration tree. However, we seem to be choosing every possible option for a list of $ m $ vertices, thus, we have at least $ O(m^m) $ configurations to check, so why is the running time of NTM $ N_1 $ polynomial? shouldn't it be exponential?

I understand that "guessing" means reaching a certain configuration. Since I have an NTM with $ O(m^m) $ possible branches, even if these branchings happen "parallelly" , I still have to perform stage 4 ( validation of edges ) for every branch, so I have a total time complexity of $ O(p\cdot m^m) $ for some polynomial $ p $. So how's the total time-complexity polynomial?

  • 1
    $\begingroup$ You are thinking of trying every possible combination and then checking them sequentially like a deterministic TM would, however a NTM would check all of the possibilities in parallel that is all $m^m$ of them, so you have to polynomial runtime (only the time it takes to check one certificate). For me an easier way to think of non-determinism is that if you choose something, you automatically guess the correct thing, that is the NTM "guesses" the correct path and then verifies it, this makes the polynomial runtime more intuitive. $\endgroup$
    – plshelp
    Jul 1, 2023 at 11:18
  • $\begingroup$ Thank you, I understand now. $\endgroup$
    – flamel12
    Jul 2, 2023 at 5:21


Your Answer

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

Browse other questions tagged or ask your own question.