posted at 2021.1.4 14:44 by 风信子
Tsp，即世界著名的旅行商问题（traveling salesman problem）的简称，何谓P和NP？克雷数学研究所官方网站上，P与NP问题描述如下：
如果一个解是否是一道题目的正确解很容易检验，那么求解这道题目是否同样容易？这就是P与NP问题的本质。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的实例，使得A和B的答案完全相同，要么都为“是”，要么都为“否”。
显而易见，在对诸多NP问题进行分类时，归约用途不小。归约能带来意想不到的有序度：经Cook证明，每个NP问题都可以归约为可满足性问题。
由于这种归约思想，复杂性理论领域变得热火朝天，Richard Karp漂亮地给出了P类、NP类、图灵机和问题解约的专业阐述，还提出了如今赫赫有名的21个NP完全问题列表，并列出了Cook可满足性定理给出的归约。列表中，Tsp以两种不同面目出现，分别是无向图的哈密顿回路问题和有向图的哈密顿回路问题。
正如Wowbagger the Infinitely Prolonged当初的那句台词一样----在《银河系搭车客指南》中，他打算挑衅宇宙中的每个男人和每个女人，当这项Tsp计划的可行性遭到质疑的时候，回答道“人总是可以有梦想的，是吧？”。
P + NP = Tsp
20646a89-e217-4dde-8b25-596065167478|0|.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Tags: 车, 方法, 类, 算法
IT技术
