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!

  • $\begingroup$ Unless I am missing something, if $x\in\mathbb F_p^n$ is a minimal-support solution of $Ax=b$ with $A\in\mathbb F_p^{m\times n}$ and $b\in\mathbb F_p^m$, it is also a minimal-support solution of the same system over $\mathbb F_{p^k}$ for any $k$ (just express a hypothetical smaller-support solution as a linear combination of $\mathbb F_p$-vectors using a basis of $\mathbb F_{p^k}$ over $\mathbb F_p$). Thus, NP-hardness of the problem over $\mathbb F_p$ implies its NP-hardness over $\mathbb F_{p^k}$. OTOH, I wouldn’t expect a simple reduction between fields of different characteristics. $\endgroup$ Feb 3 '17 at 19:52
  • $\begingroup$ Btw, the problem over $\mathbb F_2$ was shown NP-complete already in the 1978 Berlekamp paper given in the comment to mathoverflow.net/a/58494 . $\endgroup$ Feb 3 '17 at 20:03
  • $\begingroup$ Emil, thank you; I thought of the $F_{p^k}$ solution quickly, as it is directly obvious from the character and vector space structure over $F_p,$ as you stated. However, I am still struggling with primes other than $2$; I have started exploring whether it can be shown for just $F_3,$ perhaps through some modification of the initial proof. $\endgroup$ Feb 4 '17 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.