3
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Sriram
    Commented Nov 14, 2023 at 4:31
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Commented Nov 14, 2023 at 6:12
  • $\begingroup$ Thank you for the explanation! $\endgroup$
    – Sriram
    Commented Nov 14, 2023 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.