patternMinor
What is the complexity of minimising a convex quadratic function over the integers?
Viewed 0 times
convexthewhatfunctionoverintegersquadraticminimisingcomplexity
Problem
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.
$$
\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.
Solution
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.
Context
StackExchange Computer Science Q#162907, answer score: 2
Revisions (0)
No revisions yet.