Can AI Really Crack NP‑Hard Problems? Inside the DeepSeek‑R1 Breakthrough

Yesterday a news report highlighted a breakthrough where AI approaches are getting close to solving NP‑hard problems, thanks to enhanced reasoning prompts applied to models such as DeepSeek‑R1.

NP‑hard problems near AI breakthrough! Nanjing‑Oxford revamp DeepSeek‑R1 inference (Source: Xinzhiyuan)

The researchers discovered that using high‑instruction inference prompts can significantly improve the mathematical reasoning abilities of large models, potentially tackling NP‑hard challenges. The related paper is available at https://arxiv.org/abs/2502.20545 .

They constructed a dataset called SoS‑1K containing 1,000 carefully designed polynomial problems, accompanied by five expert‑level reasoning guides. These guides help LLMs simulate the thought process of mathematicians rather than merely matching patterns. Experiments showed that models like DeepSeek‑R1 and Qwen2.5 achieved up to a 21% increase in correct answers on mathematical reasoning tasks, far surpassing random baselines.

Remarkably, the 14‑billion‑parameter Qwen2.5 model discovered a new counterexample to Hilbert’s 17th problem, a milestone that previously required 27 years of human effort.

This suggests that with appropriate reasoning guidance, AI may overcome mathematical problems that have stumped researchers for decades.

Reasoning Guidance Is the Key to AI Math Ability

It does not mean that mathematics or reasoning become unimportant; on the contrary, specialized guidance is crucial.

The term "reasoning guidance" refers to highly specialized mathematical prompts that require solid theoretical knowledge, deep understanding of problem essence, and systematic, hierarchical instruction design to let AI emulate a mathematician’s thinking.

Ordinary vs. Expert‑Level Reasoning Guidance

Ordinary query: “Can this polynomial be expressed as a sum of squares?”

Expert‑level guidance: Determine whether the polynomial’s highest degree is even. Assess non‑negativity and look for symmetry or translational invariance. Match known sum‑of‑squares (SoS) cases to narrow the search. Decompose into square forms to see if it can be represented as a sum of squares. Construct a matrix and check for positive semidefiniteness.

Such guidance demands strong mathematical foundations; those capable of correctly directing AI are themselves top‑tier mathematicians.

AI‑Driven New Paradigm for Mathematical Research

Future mathematical research may follow a new workflow:

Problem formulation & modeling: Human mathematicians decide research directions and abstract real‑world problems into mathematical models.

Reasoning guidance & inspiration: Mathematicians become “reasoning architects,” building logical frameworks to steer AI’s search and deduction.

Verification & insight: AI may uncover new counterexamples, patterns, or conjectures, but humans must validate, generalize, and integrate them into theory.

Intuition & creativity: While AI excels at computation and deduction, humans provide higher‑level intuition and creative breakthroughs.

In this mode, successful mathematical research requires both deep mathematical knowledge and the ability to harness AI effectively.

Reference: Xinzhiyuan. “NP‑hard problems near AI breakthrough! Nanjing‑Oxford revamp DeepSeek‑R1 inference, crushing 27‑year human research.” NetEase News, 4 Mar. 2025. https://finance.sina.com.cn/roll/2025-03-04/doc-inennkck5794377.shtml .