LLM通过推理指令展现解决NP-hard问题潜力，甚至发现新的希尔伯特问题反例。
原文标题：NP难问题接近被AI破解！南航牛津爆改DeepSeek-R1推理，碾压人类27年研究
原文作者：数据派THU
冷月清谈：
南京航空航天大学、南通大学和牛津大学等机构的研究者发现，通过高质量的推理指令指导，类似DeepSeek-R1这样的大型语言模型(LLM)在解决数学难题——判断多元多项式是否为非负——上展现出显著潜力。这一问题与NP-hard的希尔伯特第十七问题密切相关。研究表明，在没有推理指导的情况下，LLM的准确率仅略高于随机猜测。然而，给予专家级推理指导后，模型的准确率显著提升，最高提升了21%。令人惊讶的是，Qwen2.5-14B-Instruct-1M模型甚至发现了一个此前从未见过的希尔伯特问题反例，而人类为此耗费了27年。研究者认为，LLM在解决NP-hard问题上展现出巨大潜力，并可能在未来取得突破。此外，研究还发现，专注于推理的LLM通常优于通用LLM，参数较大的模型通常只需要更少的推理步骤就能正确预测。通过对7B模型进行微调，其准确率可以大幅提升，甚至超越更大规模的模型。
怜星夜思：
1、如果LLM真的能够解决NP-hard问题，会对哪些领域产生重大影响？
2、LLM发现希尔伯特问题反例的过程是如何进行的？能否更详细地解释一下？
3、除了文中提到的应用，LLM在数学推理方面还有哪些潜在的应用场景？
2、LLM发现希尔伯特问题反例的过程是如何进行的？能否更详细地解释一下？
3、除了文中提到的应用，LLM在数学推理方面还有哪些潜在的应用场景？
原文内容
近期，南航、南通大学、牛津等机构的研究者发现：通过高指令的推理指令，DeepSeek-R1有望解决数学上的NP-hard问题！
论文地址：https://arxiv.org/abs/2502.20545
NP-hard问题，是计算复杂性理论中的一类问题。它们至少和NP问题一样难，但不一定属于NP类别（即不一定中多项式时间内被验证）。
本来，DeepSeek-R1、GPT-4o、OpenAI o1-mini这些模型，是做某种数学推理难题（SoS）是很困难的，正确率也就比纯猜高一点。
但是，一旦给它们一些推理指导，所有的模型的推理能力立马噌噌上涨，专业率最高提升了21%。
更令研究者们吃惊的是，Qwen2.5-14B-Instruct-1M在指导下，居然用了一个新奇精巧的方法，给出了一个此前从未见过的希尔伯特问题的反例：
要知道，希尔伯特问题的反例，可并非简单推导就能得出来的。
自1893年问题被提出之后，首个反例的发现耗时长达27年！
如今，却被LLM短时间内破解了。
研究者们大胆预言：照这个速度演进，LLM离破解NP-hard问题已经很近了。
LLM能解决希尔伯特第十七问题吗？
如今，LLM在众多任务上，表现已经接近人类水平，但它们在严谨数学问题求解上的能力，仍是不小的挑战。
这次，研究者决定给大模型们来一个硬核难题——判断给定的多元多项式是否为非负的。
这个问题，和希尔伯特第十七问题密切相关。后者由数学家希尔伯特在1900年提出后，立马成为23个经典数学问题之一。
而且，许多应用数学和计算数学中的关键挑战，都可以转化为判断某些多项式的非负性问题，比如控制理论、量子计算、多项式博弈、张量方法、组合优化等。
然而，判断一般多项式是否非负，是一个公认的NP-hard问题！
即使对于相对低阶或仅含少量变量的多项式，此问题仍然极具挑战性。
怎么办？为此，研究者们只能去寻找多项式的特殊类别，将复杂的非负性约束，替换成更简单一些的条件。
由此，平方和（SoS）条件就登场了。
作为一项数学技术，它通过将多项式表示为若干平方项的和，提供了一种充分但非必要的非负性判定方法。
所以，OpenAI o1和DeepSeek-R1，能解决SoS条件规划问题吗？
用一个数据集，给LLM专业推理指导
为此，研究者构建了SoS-1K数据集。
这个数据集经过了精心策划，包含约1,000个多项式，并配备了五个精心设计的专家级SoS专业推理指导。
具体包括：
-
多项式阶数
-
主导搜索方向的非负性
-
特殊结构的识别
-
平方形式表达的评估
-
单项式的二次形式矩阵分解
接下来，属于SOTA模型们的考验来了！
DeepSeek-R1、DeepSeek-V3、GPT-4o、OpenAI o1-mini、Qwen2.5 系列和 QwQ-32B-Preview在内的多位明星大模型，接受了数学难题的洗礼。
研究者们得出了一系列有趣的发现。
首先，如果未提供任何推理指导，所有的SOTA模型几乎都无法解决SoS问题。
它们的准确率基本都在60%，仅仅略高于50%的随机猜测基线。
不过，一旦使用高质量的推理轨迹进行提示，所有模型的准确率就立马有了显著提升！
最高的提升了21%，而且推理质量越高，模型表现就越好。
另外还有两点发现：专注于推理的LLM通常优于通用LLM，无论提示质量如何。
参数较大的模型通常只用更少的推理步骤，就能正确预测，而小模型要达到最佳性能，就需要更多的推理过程了。
14B模型竟发现了此前未见的希尔伯特问题反例
然后，研究者还进一步证明，对一个预训练的7B模型在SoS1K数据集上进行4小时的监督微调后，仅使用2张A100 GPU，就能让它准确率从54%暴增至70%，响应速度也大幅提高。
其中，SoS-7B仅需DeepSeek-V3和GPT-4o-mini计算时间的1.8%和5%。
也就是说，这个7B模型超越了671B的DeepSeek-V3和GPT-4o-mini在内的更大规模模型。
然后，惊人的结果来了——
当模型被输入高质量的推理提示时，甚至在研究级问题上做出了革命性的突破。
比如，Qwen2.5-14B-Instruct-1M就利用Motzkin多项式，生成了全新的、此前未见的希尔伯特第十七问题的反例。
具体来说，模型是如何发现这个反例的？
研究者展示了以下过程：通过SoS Reasoning提示，Qwen-14B-1M推导出了一个新的有效NNSoS示例：
模型构建这个例子的方法，非常新奇有趣，令研究者赞叹不已。
它从NNSoS的著名例子开始，如：
，然后，引入了一个新变量并稍微修改了系数，进而生成了q_a。
，然后，引入了一个新变量并稍微修改了系数，进而生成了q_a。
这也就给了我们极大信心：按照如今LLM展现出的推理能力，或许有朝一日，它们真能破解NP-hard问题。
值得一提的是，团队只用2张英伟达A100 GPU，耗时4小时就完成了对Qwen2.5-7B-Instruct-1M的微调。
由此得到的SoS-7B模型达到了70%的总体准确率，超过了671B参数量的DeepSeek-V3（69%），同时响应时间仅需1.8秒，而DeepSeek-V3则需要100秒。
SoS-1K Dataset
首先，研究者对SoS多项式做出了定义。
随后，研究者们为LLM精心设计了指令，从而提供了结构化的分析框架，明确了约束条件，优化了逻辑推理流程，让它们显著提高了解题能力。
为此，他们构建了三种不同层次的的推理指令集。
1. 基础SoS指令（SoS Plain）
直接向LLM提问：「请分析该多项式是否可以表示为平方和（SoS）」？
2. 简化SoS指令（SoS Simple）
将SoS多项式划分为五个不同类别，每个类别由简洁的一行标准定义。
3. 基于推理的完整SoS指令（SoS Reasoning）
这是一个结构化的五步框架，用来系统化识别SoS多项式。
而就是这个SoS Reasoning，成为了LLM解决数学研究级问题的基础，让它们的能力扩展到更复杂的数学推理任务。
下面就是一个SoS Reasoning的示例。
-
步骤1. 检查次数：SoS多项式的最高次数必须是偶数。
-
步骤2. 检查非负性：SoS多项式对所有实数输入都应为非负值。
-
步骤3. 检查已知特例：任何非负二次多项式以及任意一元或二元的非负四次多项式均为SoS。
-
步骤4. 检查平方形式：根据定义2.1，SoS多项式可表示为：p_s(x) = ∑_i{q_i(x)²}。其中，每个q_i(x)均为多项式。
-
步骤5. 检查矩阵分解：根据定理B.1，可以将多项式表示为：p(x) = y*ᵀQy*。其中，Q为对称矩阵。随后，检查Q是否为半正定矩阵。
SoS任务上的LLM评估
在SoS-1K数据集中，研究者随机抽取了约340道测试题，涵盖了所有测试子类别。
参与评估的有专门的推理模型（如DeepSeek-R1、OpenAI o1-mini 和QwQ-32B-Preview），以及通用大模型（如DeepSeek-V3、GPT-4o 和Qwen2.5系列）。
结果如下。
模型对SoS和非负性的理解
有人可能会问：
-
模型是只学会了分类，还是真正发展出了「思考」和「构建」新证明和示例的能力？
-
当面对SoS或多项式优化中的研究问题时，模型能否生成具有数学意义的见解？
为了探索这一点，团队设计了一系列研究导向的问题来测试模型理解SoS和非负性质背后数学概念的能力。
比如，问Qwen-7B-1M和Qwen14B-1M：你能提供一个文献中从未出现过的新NNSoS吗？
有趣的是，当使用SoS Plain提示时，Qwen-14B-1M只能给出文献中已知的例子，而Qwen-7B-1M返回了一个不正确的答案：
虽然回答错误，但这个问题挑战性极大，即便像YALMIP这样的经典求解器也无法提取全局最优性。
然而，当使用SoS Reasoning提示向模型提出相同的研究问题时，模型正确地识别出了pa不是问题的有效解。
这一改进源于SoS推理的第4步，其中模型认识到p_a(x)是两个变量的非负四次多项式，因此不可能是NNSoS。
进一步分析
Q1：模型是否遵循真正的数学逐步验证过程？
结果显示，LLM能够按照SoS推理指令，一步一步生成逻辑和数学都正确的答案。
比如在下面这个例子中，o1-mini的回复不仅在逻辑上和数学上是正确的，而且一旦模型推导出答案就自然停止，而不是盲目地遍历所有可能的步骤。
与标准文本输入不同，多项式是由变量、系数、指数和项组成的复杂代数表达式。因此，对于LLM来说，有效解释和提取此类结构化格式中的关键信息至关重要。
分析表明，虽然QwQ-32B-Preview在处理超过4K token长度的问题时会遇到困难，但大多数SOTA的模型都能够成功地从4K长度的多项式中提取必要的系数进行评估，并生成正确的答案。
Q3：在SoS推理的第1步到第5步中，哪一步的准确率有所提高？
图2展示了o1-mini模型在基础SoS（SoS Plain）、简化SoS（SoS Simple）和完整SoS推理（SoS Reasoning）下不同测试集的准确率提升情况。
结果显示，最简单的Test Set 1（对应步骤1）在所有提示方法下，都毫无意外地达到了100%的准确率。
得益于步骤2和步骤5，对于更具挑战性的Test Sets 2a、3.1a、5.1a–5.4a，从基础SoS到简化SoS再到完整SoS推理，也都有持续的改进。
因为，这些步骤引入了一系列用于非负性验证的数学方法，包括常数系数检查、网格求值、首项和主导项比较、寻找最小值、矩阵分解以及寻找对称性和平移。
Q4：模型在推理过程中会「偷懒」吗？
是的，在SoS推理提示下观察到的另一个有趣现象是，模型在执行第5步时往往会「走捷径」。
具体而言，它通常会避免完全执行第5步中的矩阵分解或半正定规划（SDP）等复杂操作，而是基于前面步骤的结果推测答案。这种行为在处理长输入和复杂多项式时尤为普遍。
对于较简单的问题，推理模型如o1-mini（运行时间最短，为17秒）和较大的模型如QwQ-32B-Preview往往会采取捷径，跳过第5步，从前面更简单的步骤中推断答案。
而DeepSeek-V3则不会走捷径，而是花费明显更多的时间（40秒）正确地解决所有步骤。
Q5：推理长度如何影响准确性？
如图3所示，更高性能的模型通常需要更少的思考所需token数量来做出正确预测，而性能较低的模型需要更多的推理步骤才行。
例如，DeepSeek-R1和o1-mini在1K-2K的输出长度下，就达到最高的正确预测数量；而Qwen2.5系列需要3K-4K个token才能产生正确答案。
Q6：当前的SOTA模型有什么局限性？
首先，对于长输入情况，会出现无效样本。例如，在DeepSeek-R1中，340个样本中只有234个是有效的。
其次，在处理复杂问题时，「走捷径」虽然会节省时间，但在困难步骤时过早停止并猜测答案，会对准确性产生负面影响。
第三，虽然这些模型在处理小型多项式时表现出色（准确率接近90%），但在多项式的二次型涉及低秩矩阵分解时，表现不佳。
参考资料：
https://arxiv.org/abs/2502.20545
