关于算法的理论和实践的gap

关于算法的理论和实践的gap，一直是算法研究中常被提及的话题。大部分人，包括不少本身研究算法理论的研究人员，认为算法理论确实没有很好的发挥其本应该有的功能。我自己理解主要应该有解释功能（解释问题难度和算法行为）和引导功能（引导实践算法设计）。

从解释功能讲，NP复杂性理论指出很多问题是难的（假设P!=NP），而且有许多悲观结论，典型的一个就是SAT（布尔可满足性问题，第一个被证明的NP完全问题）的强指数时间假设，而且目前SAT问题依然没有突破最平凡的界2^n. 再比如，最大团问题不存在有意义的近似算法。。。 但现实中，SAT求解器可以解决许多工业几十万甚至百万变量级别的SAT实例，最大团问题也没见过难到无法找到一定质量近似解的程度。（NP复杂性理论说明理论上存在很难的实例，但是没法构造出实例。现实中可能不会遇到“那么难”的实例。）

再从引导功能或说使用功能讲，算法理论中一个最出名的范式就是近似算法。不过那么多年过去，真的有什么近似算法在实践中发挥重要作用吗？应该说如果有，也是极其罕见的。随机算法，实践中的随机算法似乎也很少经典的理论算法那些idea。非要说，random walk算一个。

如果我们认为算法理论纯粹是数学理论（游戏），这个辩论就可以打住，也并非不可，各自发展。但是如果大家承认，算法最终是为了解决问题，理论毕竟还是要解释现实或者引导实践，那么我们就会思考，这么多年的算法理论，是否有很大轨迹依赖的成分（毕竟是在电子计算机被发明之前就有大O），而导致没有面对现实，越来越脱节。

算法理论和实践的主要研究对象不同，理论考虑极其简单的算法还有只剩下定义的问题，而计算机上的实际计算是程序和实例。有没有更具体的算法理论，可以解释为什么很多工业实例是容易的，也可能给出一些真正可以对实践有用的算法思路？

最近几年看到研究算法理论的人也在思考这个问题，期待早日见到突破。不过，也许大家特别是年轻人都有发论文的需要，我见到的算法理论方面的paper，依然是我行我素，什么时候看到具体的算法理论呢？ 想到Knuth写过具体数学了，期待有人去创造一个具体TCS方向。

- 蔡少伟，中国科学院软件研究所 研究员 博导

https://weibo.com/7743147596/ODtFfBgE6