第9章 复杂性

对于显然具有限界的整数规划问题，多项式时间算法是存在，还是不存在？我的意思是，这就是我的演说：是存在，还是不存在？

——Jack Edmonds，1991年¹

_{1. Edmonds (1991).}

随着数字不断增长，追踪旅行商的研究带来了数学、计算和工程领域的突破，也推动了无数实际应用的进展。对TSP研究者而言，这就是骄傲和快乐的源泉。可惜，一步一步推进研究的方法并没有回答最为根本的复杂性问题：我们究竟能否高效解决每一道TSP题目呢？

从这种复杂性的观点看来，通过Stephen Cook和Richard Karp的理论，旅行商的命运能与其他许多问题的命运联系起来，比如一般整数规划问题。事实上，TSP隶属于P与NP问题，而P与NP问题则跻身于七道“千禧年大奖难题”（7 Millennium Problems）之列。克雷数学研究所为每一道难题悬赏百万美金。在其官方网站上，P与NP问题的介绍如下。

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

P与NP问题常常如此公开描述，使用TSP或其改编形式来激发读者的积极性。本章中，我们会讨论旅行商问题的一般复杂性，介绍这方面的已知事实和未知空白。