[Math] the complexity of this problem

Question

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.

Answer 1

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.