  The problem of Syndrome Decoding was proven to be NP-complete in 1978 and,
since then, quite a few cryptographic applications have had their security rely
on the (provable) difficulty of solving some instances of it. However, in most
cases, the instances to be solved follow some specific constraint: the target
weight is a function of the dimension and length of the code. In these cases,
is the Syndrome Decoding problem still NP-complete? This is the question that
this article intends to answer.
