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?

  • 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$ Feb 17 '18 at 15:04
  • $\begingroup$ @ChrisPeikert Could you maybe convert your comment to an answer? $\endgroup$
    – Maarten Bodewes
    Oct 7 '19 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.