Answer to Question #190764 in Computer Networks for Alan

Question

Consider L4 = {<G> | G is a graph containing a route that visits each vertex exactly once}. L4 is not known to be in P.

Show a high-level description of a TM that decides L4 in nondeterministic polynomial time. Show your time complexity analysis of the TM.

Answer 1

Let M be the non-deterministic Turing machine.

The running time of M be $w\epsilon \Sigma^*$

The length of the shortest sequence of moves accepting w if $w\epsilon L(M)$

1 if $w\notin L(M)$

$T_M(n)= max(m|\exists w\in \Sigma^*,|w| =n)$ such that the running time of M on w is m

The complexity of the NP class is the class of languages accepted by a polynomial non-deterministic turing machine.