1
$\begingroup$

Given that the problem of finding a minimal support solution $x_0$ to any solvable underdetermined system $Ax=b$ is NP-Hard over $\mathbb{F_2}$, can we show that this problem is NP-Hard over $\mathbb{F}_p?$

This question has already been asked in MathOverflow, to little fanfare, so I thought I would try asking here as well.

I am looking for any sources or hints, but not outright answers, as I am working for this problem for a tangential part of my dissertation.

So far, I embedded the Bounded Predecessor Existence Problem (BPEP) for finite automata over $\mathbb{F}_2$ into the problem of finding a minimal support solution for $Ax=b$ over $\mathbb{F_2}$, thanks to a lead given to me last year by a poster here named Tony Huynh. The construction used in my reduction is a simple incidence matrix $A$ for the underlying graph of the automata, except with the elements $0, 1 \in \mathbb{F_2}.$ The predecessor states of the vertices of the automata are listed in the vector $x,$ and the Bounded Predecessor Existence Problem is to determine the existence of such an $x$ (called the predecessor) given the successor state $\mathbb{1}$, representing the state-vector of all $1's.$

My feeling is that the proof works brilliantly because of the reduction of BPEP from 3SAT, but the construction used to reduce 3SAT to BPEP in the paper (Sutner, "Additive Automata on Graphs") has resisted attempts to change the automata to fit BPEP to automata over finite field with values of characteristic greater than $2.$

I have also attempted to use a different angle, namely by attempting to modify Simon Foucart's proof of the NP-Hardness of the problem over the fields $\mathbb{R}$ and $\mathbb{C}$, which uses a creative reduction from the exact 3-set cover problem, but this hopeful approach has proven fruitless as well.

It feels odd having the proofs cited/shown in my dissertation for fields of characteristic $2$ and $0,$ while the proof for other prime characteristics continues to elude me after digging through multiple NP-Complete problems and not being able to connect to the case I need. But this result (for finite fields aside from characteristic 2) has not been shown in the literature, even though it is widely assumed, leading me to think the problem is easy (or has incorrectly been assumed to be easy).

Any help pointing in the correct direction would be appreciated, and I apologize if I am breaking rules posting one question in two forums.

$\endgroup$
  • 1
    $\begingroup$ I am ignorant about the complexity classes and the related results, but AFAICT the problem is equivalent to the decoding problem of finding the closest word of a linear error-correcting code. I would be somewhat surprised if the people who have worked on such things would have only covered the case $p=2$. It is the most natural, granted, but even so. If this was just stating the obvious I apologize for wasting your time. $\endgroup$ – Jyrki Lahtonen Feb 5 '17 at 7:26
  • $\begingroup$ I've been surprised at that fact as well, Jyrki. I've been through dozens of works and haven't found a word; if anyone mentions finite fields at all, they simply treat $F_2$ as the simplest case and leave it at that (see the Sutner paper mentioned above) or they just cite Garey Johnson's text (which had a "proof was in the margin of my notes" type of treatment) and wipe their hands of the need to show it. $\endgroup$ – Thomas Rasberry Feb 5 '17 at 14:08

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.