P/NP问题

澄清说明

例如，如果你有一个问题，有人说 "你的问题的答案是数字1，2，3，4，5的集合"，计算机可能能够，很快，找出答案是对还是错，但计算机可能需要很长的时间，才能真正自己想出 "1，2，3，4，5"。另一个例子包括寻找素数。检查一个数字是否是质数很容易，但首先要找到这些数字是非常困难的。对于一些有趣的、实用的这类问题，我们缺乏任何快速找到答案的方法，但是如果我们得到了一个答案，就有可能快速检查--也就是验证--答案。这样一来，NP问题可以被认为是像谜语一样：要想出谜语的答案可能很难，但一旦听到答案，答案似乎就很明显了。在这种比较（类比）中，基本问题是：谜语真的像我们认为的那样难吗，还是我们遗漏了什么？

由于这类P与NP的问题在实践中非常重要，许多数学家、科学家和计算机程序员都想证明一个一般的命题，即每一个快速检查的问题也可以快速解决。这个问题非常重要，以至于克莱数学研究所将向任何成功提供证明或有效解释来推翻它的人提供100万美元。

再深入挖掘一下，我们发现所有的P问题都是NP问题：通过解题和比较两个解决方案，很容易检查出一个解决方案是否正确。然而，人们想知道的是相反的情况。除了P问题，还有没有其他的NP问题，或者所有的NP问题都只是P问题？如果NP问题真的和P问题不一样（P≠NP），那就意味着无论我们如何努力寻找，都不可能存在解决这些NP问题的一般快速方法。然而，如果所有的NP问题都是P问题（P=NP），那就意味着新的、非常快速的问题解决方法确实存在。我们只是还没有发现它们。

由于科学家和数学家的最大努力还没有找到解决NP问题的一般的、简单的方法，许多人认为除了P问题之外还有NP问题（也就是说，P≠NP是真的）。大多数数学家也认为这是真的，但目前还没有人通过严格的数学分析证明这一点。如果能证明NP和P是一样的（P=NP是真的），那将对日常生活的许多方面产生巨大影响。由于这个原因，P与NP的问题是一个重要的、被广泛研究的话题。

例子

假设有人想通过堆放不同质量的石头来建造两座塔。人们想确保每座塔的质量完全相同。这意味着人们必须把石头放到质量相同的两堆里。如果一个人猜测出一个他认为可行的石头的分法，就很容易检查他是否正确。(要检查答案，可以把石头分成两堆，然后用天平来检验它们的质量是否相同）。因为检查这个被计算机科学家称为 "分区 "的问题很容易，比直接解决它更容易，正如我们将看到的那样，它不是一个P问题。^[]

它到底有多难解，直截了当？如果从100块石头开始，有2^{100-1}-1=633,825,300,114,114,700,748,351,602,687，或者大约6.3 x 10^{29}种可能的方式（组合）将这些石头分成两堆。如果一个人每天都能检查一个独特的岩石组合，那就需要1.3 x 10^{22}或1,300,000,000,000,000年的努力。作为比较，物理学家认为，宇宙的年龄约为1.4 x 10^{10}年（450,000,000,000,000或约4.5 x 10^{17}秒，或约为我们堆积岩石努力所需时间的万亿分之一。这意味着，如果把宇宙初开以来的所有时间都计算在内，为了检查所有不同的方式，每秒需要检查超过两万亿（2,000,000,000）种不同的岩石划分方式。

如果人们对一台强大的计算机进行编程，以测试所有这些划分岩石的方法，人们可能能够使用目前的系统每秒检查、1、{000000displaystyle 1,000,000}种组合。这意味着人们仍然需要、2、{000000displaystyle 2,000,000}台非常强大的计算机，从宇宙的起源开始工作，以测试所有的岩石划分方式。

然而，也许可以找到一种方法，在不检查所有组合的情况下将石头分成两堆。问题 "P等于NP吗？"是问是否有这样的方法可以存在的速记。

为什么重要

有许多重要的NP问题，人们不知道如何以比测试每一个可能的答案更快速的方式解决。这里有一些例子。

• 一个旅行的推销员想通过驾车访问100个城市，在家里开始和结束他的旅行。他的汽油供应有限，所以他总共只能开10,000公里。他想知道他是否能在不耗尽汽油的情况下访问所有的城市。
• 一所学校提供100个不同的班级，老师需要为每个班级的期末考试选择一个小时。为了防止作弊，所有选课的学生必须在同一时间参加该课的考试。如果一个学生上了不止一门课，那么所有这些考试都必须在不同的时间进行。老师想知道他是否可以把所有的考试安排在同一天，这样每个学生都能参加他们每门课的考试。
• 一个农民想把100个不同质量的西瓜带到市场上。她需要把这些西瓜装进箱子里。每个箱子只能装20公斤而不破损。农夫需要知道10个箱子是否足够她把所有100个西瓜运到市场。(这很微妙，如果不超过一个西瓜的重量超过2公斤，那么任何10个西瓜都可以放在每个箱子里，如果不超过10个西瓜的重量超过2公斤，那么每个箱子里都可以放一个，等等，可以快速解决问题；观察将是任何快速解决问题的关键，例如这个问题或数集问题）。
• 一家大型艺术馆有许多房间，每面墙都挂着许多昂贵的画作。画廊的主人想购买摄像头来监视这些画作，以防有小偷想偷其中的任何一幅。他想知道100个摄像头是否足够，以确保每幅画都能被至少一个摄像头看到。
• 小团体问题：一所学校的校长有一份名单，上面记录了哪些学生是彼此的朋友。她想找到一组10%的学生，他们都是彼此的朋友。

指数时间

在上面的例子中，我们看到，如果有{100displaystyle 100}块石头，就有{2100displaystyle 2^{100}种方法来划分石头的集合。对于n个{displaystyle n}岩石，有n2个{displaystyle 2^{n}组合。函数f ( n ) = n2 {displaystyle f(n)=2^{n}}是一个指数函数。它对NP很重要，因为它是解决一个问题所需的最坏情况下的计算数量的模型，因而也是最坏情况下所需的时间量。

到目前为止，对于困难的问题，解决方案需要n {2displaystyle 2^{n}}次计算。对于任何特定的问题，人们已经找到了减少所需计算次数的方法。人们可能会想出一个办法，只做最坏情况下计算次数的1%，这样就可以节省很多计算，但这仍然是×0.01( n2 ) {displaystyle 0.01\times (2^{n})}的计算。而每一个额外的岩石仍然会使解决问题所需的计算量增加一倍。有一些见解可以产生方法来做更少的计算，产生模型的变化：例如，n 2/ n {displaystyle 2^{n}/n^{33}}。.但随着n {displaystyle n}的增长，指数函数仍然占主导地位。

考虑一下安排考试的问题（如上所述）。但接下来，假设有15000名学生。有一个计算机程序，它接收所有15000名学生的时间表。它在一小时内运行并输出一个考试时间表，使所有学生都能在一周内完成考试。它满足了很多规则（没有背对背的考试，在任何28小时内没有超过2场考试，......）以限制考试周的压力。该程序在期中休息时运行一个小时，每个人都知道他/她的考试时间表，有足够的时间准备。

但第二年，又有10个学生。如果同样的程序在同一台电脑上运行，那么一小时就会变成{210displaystyle 2^{10}}小时，因为每增加一个学生，计算量就会增加一倍。这就是{6displaystyle 6}个星期!如果还有20个学生，那么

220  {displaystyle 2^{20}小时 = {1048576displaystyle 1048576}小时 ~ {43691displaystyle 43691}天 ~ {113displaystyle 113}年

因此，对于{15000displaystyle 15000}名学生，需要一个小时。对于{15020displaystyle 15020}名学生，需要{113displaystyle 113}年。

正如你所看到的，指数函数增长得非常快。大多数数学家认为，最难的NP问题需要指数级的时间来解决。

NP-完整的问题

数学家们可以证明，有一些NP问题是NP-不完全的。一个NP-不完整的问题至少和其他任何NP问题一样难解。这意味着，如果有人找到了快速解决任何NP-不完整问题的方法，他们可以用同样的方法快速解决每一个NP问题。上面列出的所有问题都是NP-完全问题，所以如果推销员找到了快速计划旅行的方法，他可以告诉老师，而老师可以用同样的方法来安排考试。农民可以用同样的方法来确定她需要多少个箱子，而女人可以用同样的方法来找到建造塔楼的方法。

因为快速解决其中一个问题的方法可以解决所有的问题，所以有很多人都想找到一个。然而，由于有这么多不同的NP-Complete问题，而且到目前为止还没有人找到快速解决其中哪怕一个问题的方法，因此大多数专家认为，快速解决NP-Complete问题是不可能的。

基本属性

在计算复杂性理论中，复杂性类别NP-complete（缩写为NP-C或NPC），是一类具有两个属性的问题。

• 它属于NP（非决定性多项式时间）问题集。任何给定的问题的解决方案都可以被快速验证（在多项式时间内）。
• 它也在NP-hard问题的集合中。那些至少和NP中最难的问题一样难的问题。NP-hard的问题不一定是NP的元素；事实上，它们甚至可能不是可解的。

正式概述

NP-complete是NP的一个子集，是所有决策问题的集合，其解决方案可以在多项式时间内得到验证；NP可以等效地定义为在机器上以多项式时间解决的决策问题的集合。NP中的问题p也在NPC中，当且仅当NP中的每一个其他问题都能以多项式时间转换为p。NP-complete是作为一个形容词使用的：NP-complete类中的问题是作为NP+complete问题。

研究NP-完整问题是因为快速验证问题（NP）的解决方案的能力似乎与快速解决问题（P）的能力相关。人们发现NP中的每一个问题都能被快速解决--如所谓的P=NP：问题集。NP-complete中的单个问题被快速解决，比NP中的每个问题也快速解决要快，因为NP-complete问题的定义指出NP中的每个问题必须可以快速还原为NP-complete中的每个问题（它在多项式时间内被还原）。[1]

实例

众所周知，布尔可满足性问题是NP完全的。1972年，Richard Karp提出了21个已知为NP-complete的问题。这些问题被称为卡普的21个NP-完全问题。这些问题包括整数编程问题，它将线性编程技术应用于整数，knapsack问题或顶点覆盖问题。