解释计算复杂性理论 [英] Explaining computational complexity theory

问题描述

据说对象的真正掌握实现时，你可以简单地解释它。遗憾的是作为一个电子工程师，我缺乏一些计算机科学的比较正式的方面。

It is said that true mastery of a subject is achieved when you can explain it simply. Unfortunately as an Electronics Engineer I lack some of the more formal aspects of computer science.

考虑到有数学的背景，你会如何解释计算复杂性理论的天真？从哪里开始进入这个非常重要的CS的话题？我理解所涉及的一些概念，但是我缺乏总体概述，让我掉入细节。

Taking into consideration that there is some background in math, how would you explain computational complexity theory to the naïve? Where to start to get into this very important topic of CS? I understand some of the concepts involved, but I lack a general overview that allows me to drop into the details.

编辑：大O符号我很清楚。我在找更多的是，这是什么P = NP问题的解释。这是一个问题P？什么是NP？什么是NP难？

Big O notation is clear to me. What I am looking more is an explanation of what is this P = NP question. What is a problem P? What is NP? what is a NP-Hard?

编辑2：一些真正伟大的答案！现在很多东西更有意义。的问题是，有时维基百科写为如果读者已经理解所涉及的所有的概念。现在有了这个快速概述许多这些文章让很多更有意义

Edit 2: Some really great answers! now a lot of things make more sense. The problem is that sometimes wikipedia is written as if the reader already understood all concepts involved. Now with this quick overview many of these articles make a lot more sense

推荐答案

Hoooo，博士生可比闪回。好了，在这里不用。

Hoooo, doctoral comp flashback. Okay, here goes.

我们先从一个决策问题的想法，一个问题，它的算法总是可以回答是或否。我们还需要两种型号的计算机（图灵机，真的）的理念：确定性与不确定性。确定性计算机是普通的计算机，我们总是想着;非确定性的计算机是一个就像我们已经习惯了，除了是有无限的并行性，让你来一个分支任何时候，你产生一个新的过程，并检查两侧。就像约吉贝拉说，当你来到了一个岔路口，你应该把它。

We start with the idea of a decision problem, a problem for which an algorithm can always answer "yes" or "no." We also need the idea of two models of computer (Turing machine, really): deterministic and non-deterministic. A deterministic computer is the regular computer we always thinking of; a non-deterministic computer is one that is just like we're used to except that is has unlimited parallelism, so that any time you come to a branch, you spawn a new "process" and examine both sides. Like Yogi Berra said, when you come to a fork in the road, you should take it.

一个决策问题属于P，如果有一个已知的多项式时间算法，得到这个问题的答案。决定的问题是NP中，如果有一个已知的多项式时间算法用于非确定性机器以获得答案。

A decision problem is in P if there is a known polynomial-time algorithm to get that answer. A decision problem is in NP if there is a known polynomial-time algorithm for a non-deterministic machine to get the answer.

已知P中的问题是平凡的NP ---非确定性的机器只是绝后患本身派生另一个进程，其作用就像一个确定性的。但是也有一些已知是既不P中也不NP问题;一个简单的例子是枚举长度为n的所有的位向量。不管是什么，这需要2 ^N 的步骤。

Problems known to be in P are trivially in NP --- the nondeterministic machine just never troubles itself to fork another process, and acts just like a deterministic one. There are problems that are known to be neither in P nor NP; a simple example is to enumerate all the bit vectors of length n. No matter what, that takes 2ⁿ steps.

（严格地说，一个决策问题是NP如果nodeterministic机器可以到达的多时间的答案，一个确定机器能的验证的该解决方案是多的时间正确的。）

(Strictly, a decision problem is in NP if a nodeterministic machine can arrive at an answer in poly-time, and a deterministic machine can verify that the solution is correct in poly time.)

但也有一些问题，这是众所周知的是NP的量没有聚时间的确定算法是已知的;换句话说，我们知道他们是在NP，但不知道他们是否在体育传统的例子就是旅行商问题的决策问题的版本（决策TSP）：考虑到城市和距离，有没有覆盖所有的城市，回到起点的路线，在不到的 X 的距离是多少？这很容易在不确定性的机器，因为每一个非确定性的旅行商来到了一个岔路口时，他总：他的克隆前往下一个城市，他们没有访问过，并在结束时，他们交换意见，看看是否任何克隆了不到的 X 的距离。

But there are some problems which are known to be in NP for which no poly-time deterministic algorithm is known; in other words, we know they're in NP, but don't know if they're in P. The traditional example is the decision-problem version of the Traveling Salesman Problem (decision-TSP): given the cities and distances, is there a route that covers all the cities, returning to the starting point, in less than x distance? It's easy in a nondeterministic machine, because every time the nondeterministic traveling salesman comes to a fork in the road, he takes it: his clones head on to the next city they haven't visited, and at the end they compare notes and see if any of the clones took less than x distance.

（然后，指数许多克隆得到打出来的，哪些必须被杀死。）

(Then, the exponentially many clones get to fight it out for which ones must be killed.)

它不知道决策TSP是否在病人：有没有已知的聚时的解决方案，但没有证据这样的解决方案是不存在

It's not known whether decision-TSP is in P: there's no known poly-time solution, but there's no proof such a solution doesn't exist.

现在，多了一个理念：给定决策问题P和Q，如果一个算法可以转化为P上的解决方案转化为在多项式时间内Q A的解决方案，它说，Q是的多时间还原的（或只是还原）为P。

Now, one more concept: given decision problems P and Q, if an algorithm can transform a solution for P into a solution for Q in polynomial time, it's said that Q is poly-time reducible (or just reducible) to P.

一个问题是NP完全问题，如果你能证明（1）它在NP，和（2）表明，它的多时间还原到已经知道是NP完全的问题。 （那困难的部分是provie中的第一的例子的NP完全问题：这是由史蒂夫·库克的库克定理。）

A problem is NP-complete if you can prove that (1) it's in NP, and (2) show that it's poly-time reducible to a problem already known to be NP-complete. (The hard part of that was provie the first example of an NP-complete problem: that was done by Steve Cook in Cook's Theorem.)

因此​​，其实，它说的是，如果有谁发现聚时解决方案的一个NP完全问题，他们已经自动获得一个用于的所有的的NP完全问题;这也意味着，P = NP

So really, what it says is that if anyone ever finds a poly-time solution to one NP-complete problem, they've automatically got one for all the NP-complete problems; that will also mean that P=NP.

一个问题是NP难，当且仅当它是至少硬为NP完全问题。找到最短路径的更多传统旅行商问题是NP难的，没有严格的NP完全问题。

A problem is NP-hard if and only if it's "at least as" hard as an NP-complete problem. The more conventional Traveling Salesman Problem of finding the shortest route is NP-hard, not strictly NP-complete.

这篇关于解释计算复杂性理论的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！