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

就在刚刚，南航、南通大学、牛津等机构的研究者发现：通过高指令的推理指令，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的回复不仅在逻辑上和数学上是正确的，而且一旦模型推导出答案就自然停止，而不是盲目地遍历所有可能的步骤。