# 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 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.$$