NP难问题接近被AI破解！南航牛津爆改DeepSeek-R1推理，碾压人类27年研究

---

  新智元报道  

编辑：Aeneas 好困

【新智元导读】给DeepSeek-R1推理指导，它的数学推理能力就开始暴涨。更令人吃惊是，Qwen2.5-14B居然给出了此前从未见过的希尔伯特问题的反例！而人类为此耗费了27年。研究者预言：LLM离破解NP-hard问题，已经又近了一步。

就在刚刚，南航、南通大学、牛津等机构的研究者发现：通过高指令的推理指令，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。

这也就给了我们极大信心：按照如今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的回复不仅在逻辑上和数学上是正确的，而且一旦模型推导出答案就自然停止，而不是盲目地遍历所有可能的步骤。

上下滑动查看

Q2：模型能否有效地从长文本多项式中提取关键信息？

与标准文本输入不同，多项式是由变量、系数、指数和项组成的复杂代数表达式。因此，对于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%），但在多项式的二次型涉及低秩矩阵分解时，表现不佳。

（文：新智元）