NP Complete, Group Element Representation

Group Element Representation

In the previous section we described a system of linear equations A*x = b, where A is a matrix, x and b are column vectors, and all entries are integers.  The solution space is a shifted lattice in n space, and finding the closest point to the origin is np complete.

The same problem can be expressed in the language of group theory.  If A is an m×n matrix, the columns of A represent n generators in the free abelian group of rank m.  these generators combine to produce the element b.  The closest lattice point, using the manhatan metric, is now the shortest representation of b using the given generators.  Finding the shortest representation of b is therefore np complete.

Recall that finding a lattice point with positive coordinates is np complete.  Translating to group theory, finding a representation of b that requires no inverses is np complete.  In other words, is b in the free monoid spanned by the given generators?

Now assume the abelian group is finite.  In other words, A*x = b is a set of simultaneous equations, but each equation is evaluated according to its own modulus.  The first equation might hold mod 5, the second equation mod 29, and so on.  Turning from rows to columns, each column becomes a generator in our finite group.  The entry Ai,j establishes the ith coordinate of the jth generator.  What is the shortest representation of the element b, using the generators defined by the columns of A?

An ntm can try all possible vectors x in parallel, looking for smaller and smaller values.  The entries in x need be no larger than the lcm of the various moduli exhibited by the m equations.  Some thought will convince you this is a polynomial time algorithm, assuming the machine is nondeterministic.

Now suppose a tm solves this problem in polynomial time.  Convert 3-sat to closest lattice point, as we did before.  The length of the vector x is twice the number of boolean variables plus three times the number of clauses.  The number of simultaneous equations equals the number of boolean variables plus twice the number of clauses.  As shown in the previous section, we need a nonzero entry for each of the boolean variables and for each of the clauses.  If this number is k, then k is the shortest possible path to b.  A solution to 3-sat implies a path of length k to b; we only need show every other path to b is longer, in spite of the modular arithmetic.

Let l be 13 times the length of x, and use this as a modulus for all equations.  Suppose we have solved the system of simultaneous equations without solving 3-sat.  The worst case equation has coefficients of 1, 1, 1, -1, -2, and -3.  If these are multiplied by ±1, the total could go as high as 9.  This has to equal 0 mod l, which is impossible.  At least one of the entries in x is 2 or greater in absolute value.  More than k steps are required to reach b.  By selecting a high modulus, the problem of finding the closest lattice point remains intact.  Therefore, finding a minimum representation of a group element with respect to a fixed set of generators is np complete.

If this holds for abelian groups, nonabelian groups are going to be even more difficult to solve.  This is the classic Rubix Cube problem.  Given a scrambled configuration, find the shortest path back to start.  Some day a computer will solve this particular problem by brute force, but the class of problems represented by this example is np complete.  There is no algorithm, other than exhaustive search, that produces the shortest path back to start.

Cyclic Groups

Instead of choosing 13 as the global modulus, select 13 for the first equation, 17 for the second, 19 for the third, and so on.  Since the moduli are relatively prime, the finite group is isomorphic to a cyclic group of order l, where l is the product of the various primes.  The generators are simply numbers in [0,l), and some linear combination of these numbers is equal to b mod l.  Finding the lowest combination, i.e. the combination that minimizes the sum of the absolute values of the coefficients, is np complete.  Constructing b from a fixed set of summands looks like a simple problem, but it's not.

Remember that the coefficients that solve 3-sat are all 0 or 1, so we can express the problem another way.  Given a modulus l and a set of generators mod l and a destination integer b, find a subset of these generators that sum to b mod l.  Once again this is np complete.

Permutation Groups

Puzzels like the Rubix Cube are usually represented using permutations.  The six moves, i.e. turning the six faces 90 degrees clockwise, become permutations, and the scrambled configuration is also a permutation.  can problems of this form be solved?

Within our system of simultaneous linear equations, the first equation was evaluated mod 13.  If x29 is multiplied by 1 in this equation, generator 29 includes a permutation of 13 objects, moving them around in a circle one step clockwise.  A coefficient of -3 implies a circular permutation 3 steps counterclockwise.  Each generator describes many circular permutations, but if you write them all out, it's not that much larger than the original set of simultaneous equations.  The notation is bulkier, but still manageable.  Finding an optimal solution to a permutation puzzle, even an abelian permutation puzzle, is np complete.