Assume that the yes-no problem of whether $x' \in F_{p^q}^{n}$ is a minimal support solution for a consistent underdetermined system $Ax=b,$ $A \in F_{p^q}^{m \times n}, b \in F_{p^q}^n$ is an NP-hard problem when $p=2$ and $q=1$. Then the same problem is NP-hard for any $p$ and $q$ in $\mathbb{N}$.
This problem has been significantly edited from an earlier question. In short, I have shown on my dissertation that finding a minimal-support solution for a consistent underdetermined system over $F_2$ is NP-Hard by embedding the Bounded Predecessor Existence Problem (or BPEP, shown by Sutner to be NP-Complete), thanks to a reference provided by Tony Hunh (sp?) on an earlier question posted on this board last year.
I am now having trouble getting off the ground with showing the same case is true for \textit{any} finite field $F_{p^q}.$ My instinct is to use a divide and conquer approach: first, find a way to embed the $F_2$ case into the $F_p$ case for $p$ any prime, then embed the $F_p$ case into the $F_{p^q}$ case to establish NP-hardness of the above problem for all finite fields.
Since the construction embedding the BPEP - which can be restated as the problem of finding a minimal odd dominating set for a graph - to my problem simply involves making $A$ into an incidence matrix for a graph (with closed neighborhoods), so that $A$ is symmetric and has diagonal of all $1's$, I figured approaching a solution by continuing to utilize this easy construction.
In Sutner's paper, he constructs a creative automata over $F_2,$ and proves NP-Completeness of the BPEP for automata over $F_2$ by embedding 3SAT via this creative construction, which effectively forces a solution to a given 3SAT instance whenever the constructed automata is assumed to have a bounded predecessor to the successor state with $1's$ for every node of this specially constructed graph (please see Sutner's paper, "Additive Automata on Graphs," for this proof). Trying to configure Sutner's construction to be over $F_p$ instead of just $F_2$ seems to have some intuitive power, but I can't get it to work.
Another intuition for $F_{p}$ given we know the $F_2$ case is NP-Hard seems to be to repeat the matrix connected from Sutner's case $2p$ times, so that the reduction presents $\phi(A) \in F_{p}^{m \times (2pn)}$ with $\phi(x) \in F_{p^q}^{2pn}$ and $\phi(b) \in F_{p}^m.$ Here, $\phi(M)$ is just $[M, \ldots, M],$ $\phi(x) = [x, \ldots, x]$ all $2p$ times, and $\phi(b)$ is the all-1's vector in $F_p.$ The intuition is that the repetition forces $\phi(x)$ to be a minimal support solution for $\phi(Ax=b)$ whenever $x$ is a minimal support solution to $Ax=b$ over $F_2,$ and vice-versa, but I can't get this to work, nor am I sure the statement is even true.
This feels like I'm missing a very easy step, since the common sense here is that $F_2$ is, in a sense, the "easiest" finite field, so that any NP-Hard problem over $F_2$ should immediately be NP-Hard over any finite field $F_{p^q}$. But it seems more likely that the case may not be as obvious as it "feels." Any nudge in the correct direction is appreciated!