【Math】P=NP问题

最新推荐文章于 2024-10-02 11:02:27 发布

大江东去浪淘尽千古风流人物

最新推荐文章于 2024-10-02 11:02:27 发布

阅读量950

点赞数

分类专栏： Math

本文链接：https://blog.csdn.net/Darlingqiang/article/details/112644648

版权

Math 专栏收录该内容

7 篇文章

订阅专栏

文章目录

- **P vs NP**

P vs NP

0 P=NP基本定义

A problem is in the class NPC if it is in NP and is as hard as any problem in NP. A problem is NP-hard if all problems in NP are polynomial time reducible to it, even though it may not be in NP itself.
在这里插入图片描述
If a polynomial time algorithm exists for any of these problems, all problems in NP would be polynomial time solvable. These problems are called NP-complete. The phenomenon of NP-completeness is important for both theoretical and practical reasons.

0.1 Definition of NP-Completeness

A language B is *NP-complete* if it satisfies two conditions

B is in NP
Every A in NP is polynomial time reducible to B.

If a language satisfies the second property, but not necessarily the first one, the language B is known as NP-Hard. Informally, a search problem B is NP-Hard if there exists some NP-Complete problem A that Turing reduces to B.

The problem in NP-Hard cannot be solved in polynomial time, until P = NP. If a problem is proved to be NPC, there is no need to waste time on trying to find an efficient algorithm for it. Instead, we can focus on design approximation algorithm.

0.2 NP-Complete Problems

Following are some NP-Complete problems, for which no polynomial time algorithm is known.

Determining whether a graph has a Hamiltonian cycle
Determining whether a Boolean formula is satisfiable, etc.

0.3 NP-Hard Problems

The following problems are NP-Hard

The circuit-satisfiability problem
Set Cover
Vertex Cover
Travelling Salesman Problem

In this context, now we will discuss TSP is NP-Complete

0.4 TSP is NP-Complete

The traveling salesman problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip

0.5 Proof

To prove *TSP is NP-Complete*, first we have to prove that *TSP belongs to NP*. In TSP, we find a tour and check that the tour contains each vertex once. Then the total cost of the edges of the tour is calculated. Finally, we check if the cost is minimum. This can be completed in polynomial time. Thus *TSP belongs to NP*.

Secondly, we have to prove that *TSP is NP-hard*. To prove this, one way is to show that *Hamiltonian cycle ≤p TSP* (as we know that the Hamiltonian cycle problem is NPcomplete).

Assume *G = (V, E)* to be an instance of Hamiltonian cycle.

Hence, an instance of TSP is constructed. We create the complete graph *G’ = (V, E’)*, where

E′={(i,j):i,j∈Vandi≠jE′={(i,j):i,j∈Vandi≠j

在这里插入图片描述

Thus, the cost function is defined as follows −

t(i,j)={01if(i,j)∈Eotherwiset(i,j)={0if(i,j)∈E1otherwise

在这里插入图片描述

Now, suppose that a Hamiltonian cycle *h* exists in *G*. It is clear that the cost of each edge in *h* is 0 in *G’* as each edge belongs to *E*. Therefore, *h* has a cost of 0 in *G’*. Thus, if graph *G* has a Hamiltonian cycle, then graph *G’* has a tour of 0 cost.

Conversely, we assume that *G’* has a tour *h’* of cost at most 0. The cost of edges in *E’* are 0 and 1 by definition. Hence, each edge must have a cost of 0 as the cost of *h’* is 0. We therefore conclude that *h’* contains only edges in *E*.

We have thus proven that *G* has a Hamiltonian cycle, if and only if *G’* has a tour of cost at most 0. TSP is NP-complete.

主要参考资料

1 P=NP问题

今天和大家一起了解个高能知识点：P=NP问题。

看到这里我们可能是一头雾水，不由得发问：

P问题是什么？
NP问题又是什么？
P=NP又是什么意思？
研究并解决P=NP问题的意义是什么？

这四个问题也是我们由表及里去理解P=NP问题的重要切入点，通过本文你将了解到包括但不限于以下内容：

千禧年世纪难题
P类问题和NP类问题特征定义
P=NP的研究和NPC问题
解决P=NP问题的大方向

2 千禧年世纪难题

时间镜头拉回2000年数学界出现了一个里程碑事件：千禧年大奖难题

千禧年大奖难题 Millennium Prize Problems 是七个由美国克雷数学研究所 Clay Mathematics Institute 于2000年5月24日公布的数学难题。根据克雷数学研究所订定的规则，所有难题的解答必须发表在数学期刊上，并经过各方验证，只要通过两年验证期，每解破一题的解答者，会颁发奖金100万美元。
这些难题是呼应1900年德国数学家大卫·希尔伯特在巴黎提出的23个历史性数学难题，经过一百年，许多难题已获得解答。而千禧年大奖难题的破解，极有可能为密码学以及航天、通讯等领域带来突破性进展。

大概意思就是2000年5月美国的一个私人非盈利机构出了7个意义重大的问题，解答任何1道会得到100w美元奖金，说到钱忽然精神起来了，不妨看下这7个多金的题目：

P/NP问题（P versus NP）
霍奇猜想（The Hodge Conjecture）
庞加莱猜想（The Poincaré Conjecture）
黎曼猜想（The Riemann Hypothesis）
杨-米尔斯存在性与质量间隙（Yang-Mills Existence and Mass Gap）
纳维-斯托克斯存在性与光滑性（Navier-Stokes existence and smoothness)
贝赫和斯维讷通-戴尔猜想（The Birch and Swinnerton-Dyer Conjecture）

黎曼猜想去年闹得沸沸扬扬，相信都有所耳闻，不过黎曼猜想是研究素数分布规律的问题，相比之下P=NP问题和计算机领域的关系更为密切，所以P=NP问题被认为是理论计算机和数学领域的综合问题，该问题的研究成果将对计算机领域和现实生活带来巨大的影响。

如克雷数学研究所的约定只要证明或者证伪P=NP问题即可赢取100w美元奖金，其实相比P=NP问题的证明或证否的影响和意义，100w奖金只是皇冠上的一粒尘埃而已。

前面铺垫了一些卖了个关子，快马加鞭一起先来看下 P和NP，到底是个怎样的问题？
在这里插入图片描述

3 P类和NP类问题特征

克雷数学研究所官网找到了关于 P和NP问题的简单说明：

在这里插入图片描述

简单意译一下：

假设你正在为400名大学生组织住宿，但是空间有限只有100名学生能在宿舍里找到位置。更复杂的是还给了你一份不相容学生的名单，并要求在你的最终选择中不要出现这份名单中的任何一对。
这是计算机科学家称之为NP问题的一个例子，因为很容易检查一个同事提出的一百个学生的给定选择是否令人满意，然而从头开始生成这样一个列表的任务似乎太难了以至于完全不切实际。
事实上从400名申请者中选择100名学生的方法总数比已知宇宙中的原子数量还要多！这类其答案可以被快速检查，但是通过任何直接的程序需要不可接受长度的时间来解决，比如300年或者更多…
斯蒂芬·库克和列昂尼德·莱文在1971年独立地提出了P(即容易找到)和NP(即容易检查)问题。

P和NP问题是斯蒂芬·库克和列昂尼德·莱文在1971年提出的，从上文的描述中大概知道了P问题和NP问题的主要特征：

P 问题(easy to find)

all problems solvable, deterministically, in polynomial time
译：多项式时间内可解决的问题(当然在多项式时间是可验证的)

NP 问题(esay to check)

non-deterministic Polynomial time
译：非确定性多项式时间可解决的问题

举几个例子来加深印象：

计算1-1000的连续整数之和：这个问题就比较简单，无论是编程还是使用高斯求和公式都可以在有限可接受的时间内完成，这种算是P类问题。

计算地球上所有原子个数之和：这个问题就很困难甚至无解，但是现在有个答案是300个，显然是错的，所以很容易验证但不容易求解，这种算NP类问题。

看到这里我们get了一个非常重要的概念(敲黑板划重点)：**P类问题是可以在多项式时间内解决并验证的一类问题**，NP类问题是可以多项式时间验证但是不确定能否在多项式时间内解决的一类问题。

等等！让我捋一捋，前面一直说 多项式时间 ，那么到底啥样的时间是多项式时间呢？

4 多项式时间

其实多项式时间的概念我们还是很熟悉的，在做算法题或者日常工作时我们都会说，这个解法的时间复杂度是O(n^2)性能不是很好，那个解法的时间复杂度是O(nlogn)(注:计算机中的log一般指底数=2)还可以。

这里的大O就是时间复杂度的表示法，看到这里仿佛清晰一些了，不过还是看下多项式表达：

a_{0} + a_{1} *{n} + a_{1} *{n}^{2}+…+ a_{k} *{n}^{k}

多项式的概念我们在小学初中的时候就开始接触了，对于计算机来说有更特别的含义，我们都知道算法时间复杂度的大O表示法，取表达式中的最高次其他项忽略，因为随着输入规模的增大最高次的影响最大，对计算机来说可以做这样的近似处理，比如上面的多项式表达式可以理解为O(n^k)的复杂度。

这个世界并不是只有多项式时间这么简单，我们还知道有指数函数形如2^{n这个计算量已经非常可怕，更不要说n}n和n!这种问题了。

对于计算机而言，它不知道问题难不难，对它而言就是拆解成非常多的步骤去执行，去衡量计算机认为难或者不难或许可以从其执行时间来看，在排除代码实现差异来说，执行时间越长的问题通常都会比较难。

我们通常将多项式时间看作是计算机解决问题的分水岭，因为超过多项式时间之后时间消耗上就不太好接受了。

直观感受一下，随着不同输入规模下，多项式时间和非多项式时间的时间消耗曲线差异吧：
在这里插入图片描述

看到这里恍然大悟，多项式时间内可解决的意义所在。

回过头看看NP问题是non-deterministic Polynomial time，也就是NP问题能否在多项式时间内解决存在不确定性。

也就是说很多NP类问题如果无法在多项式时间内解决，那么于我们当前的计算能力而言是几乎无解的，量子计算机目前还处于初级阶段，或许若干年后这些问题对于量子计算机而言是可以接受的…

或许你会问像超级计算机这种能行吗？我们从时间增长曲线来看，问题规模扩大一点点，我们需要的算力就是更大倍数的增加，这样堆砌机器不是好办法，我们最好寄托于其他解决思路。

看到这里聪明的读者会不由感叹：要是把NP问题转化到多项式时间内解决，那将是多么的进步啊！如果你已经开始有这个想法了，那也就开始深入 P=NP 的腹地了，我们继续前进~

等等！我们一直在提 NP 类问题，听着这列问题还挺有意义并且很难，能不能举几个现实的 NP 问题的例子呢？这个问题很好呀！我们来看看现实中的 NP 问题吧。

5 现实中的NP类问题

其实现实中的 NP 类问题非常多，并且很多都有非常重要的意义，举几个大家耳熟能详的例子，比如旅行商问题(又称旅行推销员问题)。

先来看下旅行商问题 TSP 的定义：

旅行推销员问题 Travelling salesman problem是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。
最早的旅行商问题的数学规划是由 Dantzig（1959）等人提出，并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难，但已经有了大量的启发式算法和精确方法来求解数量上万的实例，并且能将误差控制在1%内。

在这里插入图片描述