P与NP问题

P与NP问题，全文多项式与非确定性多项式问题,在计算复杂度(理论的一个分支计算机科学而数学)，是否都是所谓的问题NP问题实际上是P问题。P问题是一个可以在"多项式时间，这意味着一个算法对其解存在，使之步数为算法以a为界多项式的函数n,在那里n对应于问题输入的长度。因此，我们说P个问题是简单的，或者易处理的．如果一个问题的答案可以在多项式时间内被猜测和验证，那么这个问题就被称为NP问题，而非确定性问题意味着没有特定的规则来进行猜测。

线性规划问题是NP的，因为在的步骤数单纯形法由美国数学家于1947年发明乔治Dantzig，随着输入的大小呈指数增长。然而，在1979年，俄罗斯数学家Leonid Khachian发现了一个多项式时间算法。，计算步数以变量数量的幂增长，而不是指数增长，从而显示出线性编程这一发现使以前的问题得以解决棘手的问题．

问题是NP-hard是指其解决方案的算法可以被修改以解决任何NP问题或任何P问题，因为P问题是NP问题的子集。(然而，并非所有NP难问题都属于NP问题。)一个既属于NP又属于NP难的问题被称为是非完全多项式．因此，找到一个有效的算法np完全问题这意味着可以为所有NP问题找到有效的算法，因为属于该类的任何问题的解决方案都可以重铸为该类任何其他成员的解决方案。1971年，美国计算机科学家斯蒂芬·库克证明了可满足性问题(在公式中为变量赋值的问题)布尔代数是np完全问题，这是第一个被证明是np完全问题的问题，并为显示属于np完全问题类的其他问题开辟了道路。np完全问题的一个著名例子是旅行推销员问题，该方法广泛应用于优化运输时间表。不知道是否有多项式时间算法而确定这些问题是可处理的还是难以处理的仍然是理论计算机科学中最重要的问题之一。这样的发现将证明P = NP = NP-完备，并在计算机科学和许多领域发生革命性的变化数学．

例如，现代密码学依赖于假设，因式分解两个大的乘积主要的注意，验证两个质数的乘积很容易(多项式时间)，但计算两个质数因子却很难。高效的发现算法因为分解大数会破坏大多数现代加密方案。

2000年美国数学家斯蒂芬·斯梅尔他列出了21世纪需要解决的18个重要数学问题。他列出的第三个问题是P与NP问题。同样在2000年，它被指定为年问题，是美国马萨诸塞州剑桥克莱数学研究所选出的七个数学问题之一，获得特别奖。每个千年难题的解决方案价值100万美元。