Syndrome Decoding Problem

The syndrome decoding problem is the following computational problem. Given a binary parity-check matrix and a syndrome , find a vector with the minimum number of nonzero coordinates (minimum Hamming weight) such that

Here is the finite field with two elements. If and , then the solutions form the coset . Syndrome decoding is therefore equivalent to finding a nearest codeword of the binary linear code to .

Berlekamp et al. (1978) proved that the associated decision problem is NP-complete. An AI-generated reduction given by OpenAI (2026) established -factor hardness of approximation, where is the code block length.