什么是"P = NP?"，为什么它是一个如此著名的问题? [英] What's "P=NP?", and why is it such a famous question?

问题描述

在计算机科学中，P = NP是否可能是最著名的问题.这是什么意思?为什么这么有趣?

哦，为了获得额外的荣誉，请张贴有关该陈述的真实性或虚假性的证明. :)

解决方案

P表示多项式时间. NP代表不确定的多项式时间.

定义:

• 多项式时间意味着算法的复杂度为O(n ^ k)，其中n是数据的大小(例如，要排序的列表中元素的数量) ，并且k是一个常数.

• 复杂度是根据需要执行的操作数衡量的时间，它是数据项数量的函数.

• 操作是特定任务的基本操作.对于排序，基本操作是一个比较.对于矩阵乘法，基本运算是两个数的乘法.

现在的问题是，确定性与非确定性是什么意思?有一个抽象的计算模型，一个称为图灵机(TM)的假想计算机.该机器具有有限数量的状态和无限的磁带，磁带具有离散的单元，可以在其中写入和读取有限的一组符号.在任何给定时间，TM处于其状态之一，并且它正在查看磁带上的特定单元.根据从该单元读取的内容，它可以在该单元中写入一个新符号，将磁带向前或向后移动一个单元，然后进入另一种状态.这称为状态转换.足够令人惊讶的是，通过精心构造状态和转换，您可以设计一个TM，它等效于任何可以编写的计算机程序.这就是为什么它被用作证明计算机可以做什么和不能做什么的理论模型.

这里有两种与我们有关的TM:确定性和非确定性.确定性TM对于它正在读取磁带的每个符号，从每个状态仅具有一个转换.一个不确定的TM可能有几个这样的过渡，即e.它能够同时检查几种可能性.这有点像产生多个线程.区别在于非确定性TM可以生成所需数量的此类线程"，而在实际计算机上，一次只能执行特定数量的线程(等于CPU数量).实际上，计算机基本上是带有有限磁带的确定性TM.另一方面，除了可能用量子计算机以外，不能物理地实现非确定性TM.

已经证明，可以由不确定性TM解决的任何可以由不确定性TM解决的问题.但是，尚不清楚需要多少时间.陈述P = NP表示，如果问题在非确定性TM上花费多项式时间，则可以构建确定性TM，该确定性TM也可以在多项式时间内解决相同的问题.到目前为止，没有人能够证明它可以完成，但是也没有人能够证明它不能完成.

NP完全问题是指NP问题X，使得可以通过多项式约简将任何NP问题Y简化为X.这意味着，如果有人想出了一个NP完全问题的多项式时间解，那也将提供一个解决所有NP问题的多项式时间解.因此，这将证明P = NP.相反，如果有人要证明P！= NP，那么我们可以肯定，没有办法在传统计算机上解决多项式时间内的NP问题.

一个NP完全问题的例子是找到一个真值赋值的问题，该真值赋值将使包含n个变量的布尔表达式为true.
实际上，目前在非确定性TM上花费多项式时间的任何问题只能在确定性TM或常规计算机上以指数时间完成.
例如，解决真相分配问题的唯一方法是尝试2 ^ n种可能性.

The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting?

Oh, and for extra credit, please post a proof of the statement's truth or falsehood. :)

解决方案

P stands for polynomial time. NP stands for non-deterministic polynomial time.

Definitions:

• Polynomial time means that the complexity of the algorithm is O(n^k), where n is the size of your data (e. g. number of elements in a list to be sorted), and k is a constant.

• Complexity is time measured in the number of operations it would take, as a function of the number of data items.

• Operation is whatever makes sense as a basic operation for a particular task. For sorting, the basic operation is a comparison. For matrix multiplication, the basic operation is multiplication of two numbers.

Now the question is, what does deterministic vs. non-deterministic mean? There is an abstract computational model, an imaginary computer called a Turing machine (TM). This machine has a finite number of states, and an infinite tape, which has discrete cells into which a finite set of symbols can be written and read. At any given time, the TM is in one of its states, and it is looking at a particular cell on the tape. Depending on what it reads from that cell, it can write a new symbol into that cell, move the tape one cell forward or backward, and go into a different state. This is called a state transition. Amazingly enough, by carefully constructing states and transitions, you can design a TM, which is equivalent to any computer program that can be written. This is why it is used as a theoretical model for proving things about what computers can and cannot do.

There are two kinds of TM's that concern us here: deterministic and non-deterministic. A deterministic TM only has one transition from each state for each symbol that it is reading off the tape. A non-deterministic TM may have several such transition, i. e. it is able to check several possibilities simultaneously. This is sort of like spawning multiple threads. The difference is that a non-deterministic TM can spawn as many such "threads" as it wants, while on a real computer only a specific number of threads can be executed at a time (equal to the number of CPUs). In reality, computers are basically deterministic TMs with finite tapes. On the other hand, a non-deterministic TM cannot be physically realized, except maybe with a quantum computer.

It has been proven that any problem that can be solved by a non-deterministic TM can be solved by a deterministic TM. However, it is not clear how much time it will take. The statement P=NP means that if a problem takes polynomial time on a non-deterministic TM, then one can build a deterministic TM which would solve the same problem also in polynomial time. So far nobody has been able to show that it can be done, but nobody has been able to prove that it cannot be done, either.

NP-complete problem means an NP problem X, such that any NP problem Y can be reduced to X by a polynomial reduction. That implies that if anyone ever comes up with a polynomial-time solution to an NP-complete problem, that will also give a polynomial-time solution to any NP problem. Thus that would prove that P=NP. Conversely, if anyone were to prove that P!=NP, then we would be certain that there is no way to solve an NP problem in polynomial time on a conventional computer.

An example of an NP-complete problem is the problem of finding a truth assignment that would make a boolean expression containing n variables true.
For the moment in practice any problem that takes polynomial time on the non-deterministic TM can only be done in exponential time on a deterministic TM or on a conventional computer.
For example, the only way to solve the truth assignment problem is to try 2^n possibilities.

这篇关于什么是"P = NP?"，为什么它是一个如此著名的问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！