Complexity of nearest codeword in cyclic codes 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&lt;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}$.
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.