﻿ 52知识点之五：非确定型图灵机、NP复杂类-微月信

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

0 技术积累 | 2015年4月27日

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

Posted by Guy Barwell

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.

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.

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.

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理论

## 猜你喜欢

#### 发表评论

必填

选填

选填 必填，不填不让过哦，嘻嘻。

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

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