Is it $NP$-complete given $c(x),g(x)\in\mathbb{F}_2[x]$ where $g$ generates a cyclic code of length $n$ (so $g\mid x^n-1$), and $\deg c<n$ to find the nearest codeword to $c$?

This is related to the following problem in finite fields: given $\hat{g},\hat{x}\in\mathbb{F}_{2^k}$, find the sparsest polynomial $F\in\mathbb{F}_2$ such that $F(\hat{g})=\hat{x}$.


1 Answer 1


The general Nearest Codeword Problem problem for an arbitrary code is NP-hard. It is known that the problem is in NP if you only need to check whether there is a codeword within some fixed distance $\delta.$

Moreover there some efficient approximation algorithms given by Alon, Panigrahy and Yekhanin available here.

I am unaware of any work using the cyclicity property. The above apply to arbitrary linear codes.


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.