Polynomial-Factor Deterministic NP-Hardness for SVP in Every lp Norm with p > 2
2026-08-14 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors present a method that transforms a well-known hard logic problem (3SAT) into a specific version of a lattice problem called GapSVP with certain parameters (related to p-norms and a small error factor ε). Their method works efficiently (in polynomial time) for all constants p greater than 2, and also for p equal to infinity under slightly different conditions. This builds upon previous work linking related lattice problems (CVP and SVP) by combining recent constructions and reductions from other researchers. Essentially, they provide a more general way to show that approximating GapSVP is computationally difficult.
3SATPolynomial-time reductionGapSVPLattice rankp-normDeterministic reductionCVP (Closest Vector Problem)SVP (Shortest Vector Problem)Computational complexityApproximation hardness
Authors
Isaac M Hair, Amit Sahai
Abstract
For every constant $2<p<\infty$ and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we give a deterministic polynomial-time reduction from 3SAT to $M^\varepsilon$-GapSVP$_p$, where $M$ is the lattice rank. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. The reduction builds on the polynomial-gap CVP construction of OpenAI and the direct reduction to SVP for $p>2$ of Hair and Sahai [STOC'26].