P 加 NP 等于 Tsp

posted at 2021.1.4 14:44 by 风信子

        Tsp,即世界著名的旅行商问题(traveling salesman problem)的简称,何谓PNP?克雷数学研究所官方网站上,PNP问题描述如下: 

如果一个解是否是一道题目的正确解很容易检验,那么求解这道题目是否同样容易?这就是PNP问题的本质。NP问题的典型范例是哈密顿通路问题(Hamilton Path Problem):给定N座需要访问的城市(开车前往),如何访问所有城市而不重复抵达任何一座城市?给我一个解,我能轻松验证它的正确性,但是我无法如此轻松地根据我已知的方法找到一个解。

Richard Karp发明了缩写记号P,用来表示有好算法的判定问题。P类的正式定义是指,能在多项式时间内由一台单带图灵机解决的问题类,换言之,如果输入带上的符号数目为n,那么必定存在指数k和常数C,保证图灵机经过至多为Cn^k步以后必然停机。

对判定问题而言,属于P类就意味着完美。乍一看,似乎NP类远没有P类那么严格,把问题划分为NP类比划分为P类容易地多,Tsp就是一例,检验解答容易,找出解答或许很难。

实际上,对于只属于NP类而不属于P类的问题,我们居然一个也没有发现。

Stephen Cook的论文开了NP问题正式研究之先河。文中,他提出一道逻辑题可能不属于P类。“{重言式}tautology)很可能属于一组不在P内的有趣问题”。{重言式}如今则通称为可满足性问题(satisfiability problem)。Cook提出猜想的根据比该问题本身更加重要,因为他表明,每个NP问题都可以表述为可满足性问题。

Cook理论的核心思想是是归约,即把问题简而化之。例如:寻找经过给定一组点的最短路线,这并不完全等同于Tsp,因为并没有要求终点和起点重合。但是,假如我们会求解Tsp,那么只需要加入一座虚城市,令它与其他给定点之间的旅行成本均为0,就可以依样解决问题。

问题归约(problem reduction)的正式定义为,在多项式时间内,图灵机接受问题A的任意实例并据此构造出问题B的实例,使得AB的答案完全相同,要么都为“是”,要么都为“否”。

显而易见,在对诸多NP问题进行分类时,归约用途不小。归约能带来意想不到的有序度:经Cook证明,每个NP问题都可以归约为可满足性问题。

由于这种归约思想,复杂性理论领域变得热火朝天,Richard Karp漂亮地给出了P类、NP类、图灵机和问题解约的专业阐述,还提出了如今赫赫有名的21NP完全问题列表,并列出了Cook可满足性定理给出的归约。列表中,Tsp以两种不同面目出现,分别是无向图的哈密顿回路问题和有向图的哈密顿回路问题。

正如Wowbagger the Infinitely Prolonged当初的那句台词一样----在《银河系搭车客指南》中,他打算挑衅宇宙中的每个男人和每个女人,当这项Tsp计划的可行性遭到质疑的时候,回答道“人总是可以有梦想的,是吧?”。

         P + NP = Tsp

Tags: , , ,

IT技术

Add comment

  Country flag

biuquote
微笑得意调皮害羞酷大笑惊讶发呆喜欢可怜尴尬闭嘴噘嘴皱眉伤心抓狂呕吐坏笑漫骂发怒
Loading