Let $\mathbb F$ be a field (ex. a finite field, or the reals), $A$ a $m\times n$ matrix over $\mathbb F$, and $x\in \mathbb F^n$ a vector. I'm interested in finding the smallest number of coordinates I need to change in $x$ to order to have $Ax=\mathbb 0$.
What would be an algorithm to find this, or alternatively, an intractability result (ex. NP-completeness)?
Note: I am thinking of this in the context of matrix rigidity.