1
$\begingroup$

Short Integer Solution ($ SIS_\gamma^{(q,n,m,\beta)}$): Given a matrix $A\in Z_{q}^{n×m}$, find $x \in Z^m $, such that $Ax=0\mod q$ and $||x|| \le \beta$

Is $SIS\in NP$ ?

If $SIS \in NP$, then it should be reduced to any NP-complete problem.

Is there any reduction from $SIS$ to a Hamiltonian cycle?

$\endgroup$
  • 2
    $\begingroup$ Yes: the witness is such an x; it can be efficiently checked that it satisfies the conditions. The Cook-Levin theorem gives a reduction from any NP problem to SAT, which we know how to reduce to Hamiltonian cycle. $\endgroup$ – Chris Peikert Feb 17 '18 at 15:04
  • $\begingroup$ @ChrisPeikert Could you maybe convert your comment to an answer? $\endgroup$ – Maarten Bodewes Oct 7 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.