Prev: *** Evening Seminar by Prof Mike Hinchey, 28 Jan, UK: Evolving Critical Systems
Next: Algorithmic Random Oracle
From: zhuguohun on 20 Jan 2010 07:10
Let me give a simple example to show how to understand the guess concept of NDTM.
(you can also view this idea from http://zhuguohun.blog.163.com/blog/static/128376378201002075927666/)


Example: Determine a Hamiltonian cycle on NDTM by given graph G(V,E) with n vertices ( v1,v2,...Vn).



Firstly, the NDTM can guess there exists an order (x1,x2,..........xn) of G, where x1=vi( i<=1<=n)
At first glance, the number of the order can be (n-1)! / 2 .

But if we draw this order with a binary tree T.
the root of T is v1, the nodes of second level could be v2 if (v1,v2) $\in$ E, v3 if (v1,v3) $\in$ E, .......
then the third level T could be (v3,...vn) , . ......
the last level (leaf of T) could be vn, ....

So the high of T is $<=n$, and the width T of is also $<=n-1$.
Now , it is easy to understand that the NDTM can be choice the root of T and
then guess a node in parallel in second level, at last to the leaf.

So the guess is at most O(n*log2n) for NDTM instead of exponential times.


BTW,(1) I can not access "comp.theory|Google Groups"
from my campus, so I register here again and hope to exchange idea with this group.
(2)
----------------

Guohun Zhu
blog: http://zhuguohun.blog.163.com/



---
frmsrcurl: http://compgroups.net/comp.theory/NP-Completeness-from-Computers-and-Intractability
First  |  Prev  | 
Pages: 1 2 3 4
Prev: *** Evening Seminar by Prof Mike Hinchey, 28 Jan, UK: Evolving Critical Systems
Next: Algorithmic Random Oracle