# What is the complexity of minimising a convex quadratic function over the integers?

The problem of interest is $$\min_{x\in\mathbb{Z}^n} \frac{1}{2}x^\top Q x + c^\top x$$ where $$Q$$ is a positive definite matrix. I am reasonably sure this can't be solved in poly-time, since the closest lattice vector problem (in $$\ell_2$$ norm) can be reformulated in the above form. Do we have a proof of $$\mathsf{NP}$$-hardness for a corresponding decision problem - does there exist $$x\in\mathbb{Z}^n$$ so that the above quadratic takes a value less than or equal to $$f^* \in \mathbb{R}$$?

I don't find a proof of $$\mathsf{NP}$$-hardness of the closest lattice vector problem in $$\ell_2$$ norm. If such a proof is found, then this problem is solved.

• – D.W.
Nov 13, 2023 at 20:03

The closest lattice vector problem is NP-hard in the $$L_2$$ norm. See NP completeness of closest vector problem for a reference to the proof.
• Thank you. There seems to be some inconsistencies among the links/answers. For example, the answer in the link you posted says "the shortest vector problem is $NP$-hard for any $L_p$ norm other that $L_\infty$". The cited paper by Micciancio also seems to suggest that it is hard under reverse unfaithful random reductions (and possibly not in general). Does that affect the original question? Nov 14, 2023 at 4:31
• @Sriram, that's not what it says. It says "it is not known that...". Saying "It is not known that X" is different from saying "X". It is known that SVP is NP-hard for $L_\infty$. For $L_p$ with $p \ne \infty$, it is not known whether SVP is NP-hard (but there is evidence that it is hard). No, this doesn't affect my answer or the original question, as you are not asking about SVP -- you are asking about CVP.