Breakthrough Tracker record
A deterministic NP-hardness claim for the Euclidean shortest-vector problem
Wan claims a deterministic polynomial-time reduction proving that γ-GapSVP in the ℓp norm is NP-hard for every finite p and every approximation factor γ below 2^(1/p). At p = 2, this includes exact Euclidean SVP and approximation factors below √2, removing the randomness used in earlier hardness reductions.
← Back to the filtered Breakthrough Tracker
- Stable ID
math-svp-euclidean-deterministic-np-hardness-2026- Revision
math-svp-euclidean-deterministic-np-hardness-2026.v1- Field
- Mathematics · Number theory and computational complexity
- Evidence
- Tier 1 · Peer reviewed: No
- Record state
- Provisional · Expanded preprint claim; independent review pending
- Last checked
AI role
No substantive AI role was disclosed in the inspected arXiv metadata or version-three manuscript.
Record details
- Problem or result
- Van Emde Boas’s 1981 conjecture on deterministic NP-hardness of the shortest-vector problem in Euclidean space
- Authors
- Daqing Wan
- Institutions
- Center for Discrete Mathematics and College of Mathematics and Statistics, Chongqing University
- Result date
- First submitted March 28, 2026; expanded version 3 submitted July 22, 2026
Why it matters
The Euclidean shortest-vector problem is a foundational lattice problem. Deterministic NP-hardness had remained open since van Emde Boas posed it in 1981, despite Ajtai’s 1998 randomized reduction and later randomized approximation-hardness results.
Limits
This is an expanded version-three preprint, not a peer-reviewed or independently validated theorem. No specialist correctness assessment or journal record was located. The result concerns worst-case computational hardness under the paper’s reductions; it is not a polynomial-time algorithm, a proof that P differs from NP, or evidence that deployed lattice cryptosystems are broken.
Sources
- Primary: Daqing Wan, NP-hardness of SVP in Euclidean Space, arXiv:2603.27398v3
- Independent: Bennett and Peikert, 2023 randomized hardness construction and derandomization barrier
- Independent: Simons Institute Lattices '22 open-problems context
Correction and revision history
- 2026-07-23 — Added as a provisional claim after the expanded version-three manuscript exposed the exact deterministic reduction, theorem range and relationship to the 1981 conjecture; no independent correctness assessment was located.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.