注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

P对NP的世界

Polynomial时间和指数时间的比赛

 
 
 

日志

 
 

On the guess concept of NDTM  

2010-01-20 19:59:27|  分类: 图论中NP问题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
When I view this  post,I think that the guess concept of NDTM is not easy to understand.
   http://compgroups.net/comp.theory/NP-Completeness-from-Computers-and-Intractability

The following questions is more difficult?

What if there are exponentially many structures
S (as a function of input length)? What if the
only right one of the exponentially many Structures
is guessed last?

one of answer: You can think of a NTM as exponential size set of TM's. 

In my view, this is easy to confuse the beginner.  So I give a simple example  to show how to understand the guess  concept of NDTM.

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.


  评论这张
 
阅读(333)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017