# What is the complexity of this problem?

Recently on Dick Lipton and Ken Regan's blog there was a post about problems of intermediate complexity, that is, NP problems that are harder than P but easier than NP-complete. The main message of the post was that most examples of natural questions that have been conjectured to be intermediate have subsequently been shown not to be -- the two most notable exceptions being the discrete logarithm problem (and factoring), and the graph isomorphism problem. There have been related questions here on Mathoverflow and also on TCS stackexchange.

I asked about the status of one particular problem in a comment on the blog post but got no answer, so I'll ask it again here. The problem is the following. You're given a non-singular $n\times n$ matrix over $\mathbb{F}_2$ and asked to determine whether it can be reduced to the identity using at most m Gaussian row operations. It seems very unlikely that this problem is in P, since the problem of finding an explicit matrix that needs a superlinear number of operations is open (and, I think, thought to be hard). On the other hand, if I try to take a problem like 3-SAT and reduce it to this one, I don't have any idea where to start. But that is very weak evidence for the assertion that the problem is not NP-complete, so I'm asking again the question I asked in the blog comment: is anything known, or intelligently conjectured, about the status of this problem?

The question can be reformulated as asking for the length of the shortest path between two vertices in a certain Cayley graph. (NB, that doesn't make it polynomial-time because the number of vertices in the graph is exponential.) I'd be just as happy to be told that the same problem in a different Cayley graph was probably of intermediate complexity: I chose the Gaussian elimination example because I happen to like that graph.

-
Maybe reducing the problem to asking for solutions of multivariate polynomials equations over $\mathbb F_2$ would work. Consider the equation matrix equation $g_1 g_2 \cdots g_n A = I$ where $g_l = (x_{lij})_{1\leq i,j\leq l}$ and the $x_{lij}$ form a collection of $n^3$ indeterminates. The single matrix equation actually is $n^2$ multivariate polynomial equations. Maybe requiring that the $g_i$ being of the form g_i = [I+(off diagonal) or Permutation] is the same as putting algebraic constraints on the coefficients (det g_i =1 and [some algebraic condition like nilpotence] for off diagonal). –  Taylor Dupuy Jul 9 '11 at 14:28
I ran out of space... Then existence of a solution is the same as an Ideal membership problem which is NP complete? I don't know if that helps. Maybe I'm way off. –  Taylor Dupuy Jul 9 '11 at 14:29
One potentially way off suggestion deserves another: I suggest reducing Graph Isomorphism to this, and then try a reduction in the other direction. After that I might suggest reducing one of the problems from Garey and Johnson to this. Register Allocation might be promising. Gerhard "Left Field Can Be Fun" Paseman, 2011.07.09 –  Gerhard Paseman Jul 9 '11 at 15:46
An idea: Instead of considering full rank matrices, consider arbitrary matrices. In such a case, one can consider the following. Given a matrix M (in F_2) and a vector b, what is the minimum hamming weight of a vector x such that x^tM=b. I've convinced myself that a progress argument shows that this is equivalent to asking for the number of row operations needed to transform M with a zero row at the bottom into M with a row b at the bottom. This hamming-weight problem seems related to known problems such as set-cover (but one needs to be careful over F_2 (or even Z)). –  miforbes Jul 11 '11 at 3:31
Perhaps a title such as "The complexity of minimum distance in cayley graphs" would be more informative. –  miforbes Jul 12 '11 at 0:22

This is not a full answer, but perhaps too long for a comment.

Your question is about the distance problem in a fixed Cayley graph. If one also considers the Cayley graph as part of the input then some things are known. This makes sense in the context of permutation groups, where we can explicitly give the generators in a succinct way.

Even and Goldreich in the paper "Minimum-Length Generator Sequence Problem is NP-Hard" (J. ALGORITHMS. Vol. 2, no. 3, pp. 311-313. 1981) showed:

We examine the following questions: (1) Given a set of generators of a permutation group G and a target permutation P, find (the length of) a shortest generator sequence realizing P. (2) Given a set of generators of a permutation group G, find the minimum upper bound on the length of generator sequences needed to realize any permutation in G. We show that both problems are NP-Hard by reducing the 3XC problem to each of them. The reductions we use show that these results hold even if the given set of generators is restricted to contain for each generator its inverse, too.

This actually makes the problem NP-Complete (when the length is written in unary).

In other work, Mark Jerrum in "The complexity of finding minimum-length generator sequences" (Theoretical Computer Science Volume 36, 1985, Pages 265-289) showed:

The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target permutation which is a member of the group, what is the shortest expression for the target permutation in terms of the generators? The general problem is demonstrated to be Image -complete and, indeed,is shown to remain so even when the generator set is restricted to contain only two permutations. The restriction on generator set cardinality is the best possible, as the problem becomes soluble in polynomial time if the generator set contains only one permutation. An interesting feature of this problem is that it does not fall under the headings of ‘two person games’ or ‘formal languages’ which cover the great majority of known Image -complete problems. Some restricted versions of the problem, in which the generator set is fixed rather than being part of the problem instance, are also investigated and shown to be computationally tractable. One result of this kind is that determining the most compact expression of a permutation in terms of ‘cyclicly adjacent transpositions’ can be achieved in polynomial time. Thus, from an initial arrangement of distinct objects on a circle, one can quickly compute the smallest number of interchanges of adjacent objects required to realise any other arrangement. Surprisingly, this problem appears substantially more difficult to solve than the related one (for which a solution has been known for some time) in which the objects are arranged on a line segment.

Note that Jerrum considers the length of the path in binary, which changes things.

-
It's worth mentioning that determining permutation group membership is doable in polynomial time, as shown by Sims/Furst-Hopcroft-Luks (eg, see "Polynomial-time algorithms for permutation groups" by FHL). –  miforbes Jul 11 '11 at 3:33
Thank you for that interesting answer. In my comment on Dick Lipton's blog I stressed more the importance of the fact that I was looking at a fixed Cayley graph because without that the problem felt much more likely to be NP-complete. But it's nice to have pointers to actual results of that kind. –  gowers Jul 11 '11 at 13:37

If one relaxes the question to asking the row-reduction distance of arbitrary matrices over $\mathbb{F}_2$ then it can be shown that the problem is $NP$-Complete. That is, consider

RRD (Row Reduction Distance):

Input: $m\times n$ matrices $M$, $N$ over $\mathbb{F}_2$, and an integer $k$

Output: Whether $M$ can be row-reduces to $N$ in $\le k$ steps

The claim is that this problem RRD is $NP$-complete. It is within $NP$, so the hardness is all that remains. To do this, consider the following related problem.

MHW (Min Hamming Weight):

Input: $P\in\mathbb{F}_2^{m\times > n}$, $b\in\mathbb{F}_2^n$, integer $k$

Output: Is $b$ expressible as a linear combination of $\le k$ rows of $P$.

I'll first show that MHW reduces to RRD, then show that RRD is $NP$-hard. This together will show RRD is NP-hard.

Let $(P,b,k)$ be an instance of MHW. Create $M$ and $N$ as $(m+1)\times n$ matrices, where $M$ is just $P$ with the zero row appended on, and $N$ is just $P$ with the row $b$ appended on. I'll now show that $b$ is expressible as a linear combination of at most $k$ rows of $P$ iff $M$ is row-reducible to $N$ it at most $k$ steps.

The forward direction of this claim is straightforward. Now for the backward direction. Row-reduction operations over $\mathbb{F}_2$ are just "add this row to that row", or "swap this and that row". It follows that in $\le k$ row-reductions have at most $k$ "source" rows of where the additions come from. Thus, the last row of $N$ is equal to the last row of of $M$ (which is zero) plus at most $k$ other rows of $M$. This is exactly what was wanted, as the last row of $M$ is just $b$.

This completes the proof that MHW reduces to RRD.

Now let's show that MHW is NP-hard. We'll do so with:

SET-COVER

Input: Sets $S_1,\ldots,S_m\subseteq[n]$, integer $k$,

Ouptut: Decide if $[n]$ is the union of $\le k$ of the sets $S_i$

It is know that Set-Cover is NP-complete. Here we need a slightly stronger version of this fact, where all of the sets are of constant size, and this is still NP-complete. (To see this, one first shows that 3SAT is still NP-complete when each variable appears in at most 3 clauses. Then one runs through the "standard" reduction from 3SAT to Set-Cover, and notices that all of the sets are of constant size).

Now consider a set-cover instance. Note that if we through in all subsets of each $S_i$, the answer to the cover question doesn't change. Note that we can do this as each subset is of constant size, so there aren't too many subsets to add. Thus we get

Hered-Set-Cover

Input: Let $\mathcal{S}\subseteq > 2^{[n]}$ be a family of sets, each of size $O(1)$, that is subset closed. Let $k$ be an integer.

Ouptut: Decide if $[n]$ is the union of $\le k$ of the sets from $\mathcal{S}$.

and Hered-Set-Cover is NP-complete, as argued above. We'll now reduce Hered-Set-Cover to MHW. Take a Hered-Set-Cover instance, with the family of sets $\mathcal{S}$ and integer $k$. Suppose there are $m$ sets. Then write out $P$ to be the $m\times n$ matrx where the rows are the indicator vectors for the sets in $\mathcal{S}$. The target vector $b$ is the all ones vector, and $k$ is as in the original problem. So if $b$ is a $\le k$ linear combination of the rows, then this immediately gives the set-cover of $\le k$ sets. If there is a set-cover of $\le k$ sets, then we can always pass to subsets so that each element in the ground set is covered exactly once, and thus when we sum up the relevant vectors in $\mathcal{F}_2$ we never run into the issue that 2=0.

So really we are doing a "set-cover with odd covering at each vertex" in the MHW instance. The point is that allowing the subsets in the family makes the exact number of coverings irrelevant, and so we can assume things are covered exactly once.

It seems like there might be a more direct reduction from the problem Exact-Cover (where in set-cover we require that each element be covered exactly once). Indeed, I sort of just untangled the reductions needed to use Exact-Cover. But Exact-Cover doesn't seem exactly right, because if $b$ is a $\le k$ linear combination this doesn't immediately translate to an exact cover.

This approach doesn't seem to address the issue when $M$ and $N$ are full-rank in the RRD problem, as the reduction of MHW to RRD needs non-full-rank, and the MHW problem is solvable in polynomial time when $P$ is full rank.

-
You can also find a proof that MHW is NP-complete in "On the Inherent Intractability of Certain Coding Problems" (1978) by Berlekamp, et al. authors.library.caltech.edu/5607/1/BERieeetit78.pdf –  mhum Jul 13 '11 at 8:11
@mhum: Thanks, I had an inkling that MHW might be related to some coding theory problems, but was only aware of the NP-hardness of computing minimum distance. To summarize the proof by Berlekamp et al, they basically do a reduction from 3-Dimensional-Matching, which is essentially a restricted version of exact-cover. They avoid the need to make the family of sets subset closed because any matching must have a certain size, so even if a bunch of sets cover the entire ground set, it can only be a matching if it has the required number of elements. –  miforbes Jul 13 '11 at 18:20