RSS订阅信息安全技术跟踪与研究:技术、平台、会议、论文、产业
你现在的位置:首页 / 技术积累 / 正文

52知识点之五:非确定型图灵机、NP复杂类

0 技术积累 | 2015年4月27日
转载申明:本站原创,欢迎转载。但转载时请保留原文地址。
原文地址:http://www.vonwei.com/post/5outof52.html

 

52 Things: Number 5: What is meant by the complexity class NP?

Posted by Guy Barwell

原文链接:http://bristolcrypto.blogspot.com/2014/11/52-things-number-5-what-is-meant-by.html

 

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. We continue the Complexity Theory section with NP...

Last week, Ryan introduced us to complexity classes, and in particular to P:

 is the class of languages decidable in polynomial time by a deterministic Turing machine.

This week, we introduce another complexity class: 

NP is the class of languages decidable in polynomial time by a nondeterministic Turing machine.

      维基百科:如果不加特殊说明,通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于,在计算的每一时刻,根据当前状态和读写头所读的符号,机器存在多种状态转移方案,机器将任意地选择其中一种方案继续运作,直到最后停机为止。

       确定型图灵机多项式时间可判定的语言类称为P类问题(上一个知识点已经介绍);而非确定型图灵机多项式时间内可判定的语言类称为NP类问题。至于PNP之间是否等价,这就更难了,目前还是一个开放难题,没有解决。

What is a Nondeterministic Turing Machine (NDTM)?

Well, an NDTM is a Turing Machine for which the transition function can have multiple values for the same tape value/state pair (meaning it is not technically a function any more, so the correct thing would be to call it a transition relation). Thus evaluation of an NDTM on any particular input can be thought of as a tree, branching at each point the transition function provides more than one possible value. Now, an NDTM evaluates all of these possible branches at once, and accepts if at least one of these computations halts in the accept state. This definition generalizes from language membership to decision to computational problems in the same way as P did in last weeks blog.

这段介绍非确定型图灵机NDTM的概念,即其图灵机的转换函数不再是一个具体函数,而是有多个值可选。给定一个值,对NDTM的评估可以被认为是个树,每个分支处转换函数可以提供多个值。NDTM同时计算所有可能的分支,只要至少有一个计算在accept状态停机,则NDTM就是accept的。

 

Some Examples of NP problems

We begin with an easy example: path finding. Given a directed graph (on n vertices) is there a path from vertex A to vertex B. How do we know this is in NP? Well, there is an NDTM that solves it, which basically works by simply trying every route by branching each time there is a junction. If one of these branches (ie one of the trial routes) reaches B, then that branch terminates in the accept state. Any branch that does not reach B within n steps (ie after traversing n edges) terminates in the reject state. Since any path will involve at most n-1 edges, any valid route will be detected, and so this machine correctly decides whether the path exists.

以“路径搜索问题为例来描述NP问题。给定一个有向图(n个顶点),是否存在从一个顶点A到另一个顶点B的路径?如何确定该问题是否NP呢?比较幸运的是,存在一个NDTM可以解决这个问题,每次出现交叉点时通过分支尝试每个路由路径即可,如果存在一个路径能够达到B,那么这个分支会以accept状态终止。如果某个分支在经过n步后依然无法达到B,则以reject状态终止。由于每条路径最多出现n-1条边,任何有效的路由都会被检测到,这样机器就能正确的确定路径是否存在。

One of the key examples of an NP problem is the satisfiability problem:

·                     SAT: Given an expression in n boolean variables, is there an assignment of the variables such that the expression evaluates to True?

For example, the expression (AB)(A?B) is satisfiable, with one valid assignment being A=B=True. Note that in it's standard form, SAT is a decision problem: it suffices to decide whether such an assignment exists, we don't have to find it.

       NP问题的另外一个非常重要的例子是SAT问题(布尔可满足性问题)。即给定一个存在n个布尔变量的表达式,是否存在一组赋值使得该表达式结果为True?注意,这是一个判定性问题,只是确定是否存在可满足的赋值,而不是去找到这组赋值。

Ok, so there are problems in NP. What is interesting about it?

Firstly, we see that P?NP since a DTM is an NDTM that just happens not to ever branch (in fact, our first example can actually be solved by a DTM and so is within P). So, the real question is what sort of things can we do in NP that we couldn't do in P? Well, this is the root of the P=?NP millenium problem, which is a major open problem. There are certainly problems that we have found that are known to be in NP that we do not know to be in P, but perhaps future research will show that these are also in P.

       如果一个问题属于P类问题,说明确定型图灵机DTM可解,而DTM显然是NDTM的一个特例(只有一个分支),因此该问题在NDTM中也可解。也就是说,P类问题肯定是属于NP类问题,但是反过来是否成立却不得而知。这就是著名的“P是否等价于NP”难题,已经存在很多年了。目前有些问题已经被发现属于NP,但是无法确定是否属于P,可能将来的研究能发现它们是否也在P中。

 

Lots of interesting cryptographic systems (particularly in the public key setting) are secure based on the assumption that a computational problem is "hard", which generally means "at least as hard as any problem in NP". That is, many schemes are based on problems which we think are difficult to solve, and that if you can create an algorithm that solves them you could also use this algorithm to solve lots of other problems that we currently believe to be difficult.

很多密码系统(特别是公钥系统)的安全都依赖一个计算难题,这些难题通常意味着“至少和NP中的问题一样困难。如RSA依赖的大数分解问题,ECC依赖的离散对数问题等。如果你能发明一个算法解决其中一个问题,你就可能解决一堆类似困难的问题。当然,如果你能有效的解决这些难题,这些密码机制和系统都要重新改写了。

 

The Cook-Levin theorem provides an interesting result in this direction: No problem in NP is any harder than SAT. What his means is that if I had an oracle (basically an algorithm that I can see the input/output of but none of the workings) that solved SAT, by asking it to solve cleverly constructed queries I could use it to solve any other NP problem. This made SAT the first example of an NP-complete problem. So, to show that a problem X is at least as hard as solving an NP problem (it is NP-hard), it suffices to show that if I could solve X, I could use it to solve SAT.

         Cook-Levin定理在这个方向提供了一个有趣的结论:NP中的问题不会难于SAT问题。也就是说,如果你能解决SAT问题,你就能解决NP中的所有其他问题。通常,与SAT问题一样难的问题通常称为NP完全问题,SAT实际上是第一个发现的NP完全问题。NP中任何问题都可以在多项式时间内规约为SAT问题。


  • ------------------分隔线----------------

  • 如果感兴趣,欢迎关注本站微信号,跟踪最新博文信息,手机微信扫一扫下面的二维码,即可关注!
  • 微月信公众号
  • 推荐您阅读更多有关于“ 52知识点   ”的文章

    请填写你的在线分享代码
    上一篇:[转]P vs. NP:从一则数学家谋杀案说起下一篇:52知识点之六:NP理论

    猜你喜欢

    评论列表:

    发表评论

    必填

    选填

    选填

    必填,不填不让过哦,嘻嘻。

    记住我,下次回复时不用重新输入个人信息

    本站介绍
    最近发表
    本年最热文章
    本月最热文章
    网站分类
    文章归档