许可：关于算法的一些思考

时隔一年，终于又听到许可老师讲课了

计算机学科的算法研究简介

最大团问题的思考

计算机学科关于算法的定义

算法：设计有限条规则或指令的序列，在有限步得到正确的输出

最大团问题

给定一个图，寻找一个含顶点数最多的团

如何评价算法的优劣

理论分析
严格，实际不可行
算法标准测试集
1992-1993，美国离散数学与理论计算机科学中心，DIMACS
2004-2005，许可，BHOSLIB

最大团的20年挑战难题

时间	成绩
2005.02	许可教授构造4000顶点，最大团100点的图
2005	找到96个点
2007	找到97个点
2010	找到98个点
2011	找到98个点
2014	找到99个点

P/NP问题的思考

计算是科学吗？

维特根斯坦 vs 图灵
维特根斯坦：物理命题包含时间因素，而数学命题不包含时间因素
图灵：如果说一个数学命题很难呢?
计算不是数学，也不是物理，可以说计算形似数学，神似物理（是客观存在的基本规律，且用逻辑的方式证明）

P/NP问题

P=求出的问题的解很容易
NP=验证问题的解很容易
容易验证的问题是否也容易求解？

NP完全问题

NP，即 Nondeterministic Polynomial time（非确定性多项式时间）
对于一个问题，如果存在一个算法能够在多项式时间内验证一个给定的解是否正确，那么这个问题就属于 NP 类

NP完全问题的里程碑

1971 Cook-Levin定理
1972 21个NP完全问题
1979 NP完全问题的书

人工智能会取代天才吗？

天才具有创造力 vs 常人欣赏创造力
从计算机来看是否有本质区别？

难解问题的本质

算法的本质就是机械性
算法设计的本质就是压缩
计算复杂性的本质就是压缩的极限
组合问题都能压缩吗？是否存在不可压缩的组合问题？

算法发展的两条路线及趋势

图像分类问题
问题的描述依赖与暑假，无法抽象定义为一个数学问题

算法研究的两条路线

数据—>问题—>算法
算法是语法的有穷序列，设计算法就是用语法代替语义
优化算法属于理性主义，以语义为中心
学习算法属于经验主义，以数据为中心

学习还是优化

基于大数据的算法设计方法提高了算法的生产效率，带来了算法偏见和算法黑箱问题
学习还是优化，这是个问题

学习与优化终有一战

背景：大数据被大公司垄断
关系到数据霸权能否被打破

优化算法求解极其学习问题

基于结构信息原理的结构优化算法不依赖数据
人天生具有对全局信息的处理能力

我的思考

去年的这个时候，我和一群当时大三的同学们坐在教三的某个屋子中，同样听许老师讲同样题目的讲座。犹记得去年我听后的感受只有无限的膜拜与敬仰，被许老师身上的书生气深深折服，今年不止于此，也多了一份别的感受。

其实许老师的讲座全程只回答了两个问题：为什么学习类方法会占优？为什么要坚持优化类方法？结合许老师所讲内容，我认为：当前人类所面对的问题，不是人脑能通过整合全局信息而找到最优化方法的（特别是np hard问题），所以机器学习这种黑箱方法便会大行其道。学习类方法占据市场带来的恶性效应便是数据成为了算法的衡量指标（参考百模大战），垄断大数据的大型公司便垄断了话语权。因此，更需要在这种情况下寻求不刚需数据的优化类方法的出路。

我在中学时是由衷地喜欢优化算法的：将O(n^2)一步步优化成O(nlog)的过程，对我来说充满着乐趣。然而大学后，身边的老师同学都在一股脑地搞学习，说这个才是未来。最近做课题时我也有些染上了这种”规矩“，觉得不是学习，就有些掉价。细细想来，如果我的眼界不被机器学习所限的话，一定能到更开阔的境界吧。

我不禁又想起许老师被很多知乎er抨击的GPT-4在97轮对话中探索世界难题，给出P≠NP结论，这正是许老师的过人之处：他想用学习的方法反哺优化类算法，以推动优化算法边界的拓展。一年过去，再上谷歌学术搜索，《Large Language Model for Science: A Study on P vs. NP》被引用了14次，不知道许老师对这个结果是否会满意呢？希望有生之年，能有幸看到”轻舟已过万重山“的日子。

最后附首诗

三垂冈

英雄立马起沙陀，奈此朱梁跋扈何。

只手难扶唐社稷，连城且拥晋山河。

风云帐下奇儿在，鼓角灯前老泪多。

萧瑟三垂冈畔路，至今人唱《百年歌》。

2024.9.2