13
$\begingroup$

Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence of alternate negative signs (lack of which makes computing permanent is $ \#P\mbox{-}hard$ ie. harder then $NP\mbox{-}C$ problems). This leads to some sort of symmetry in determinant, eg exchange of a pair of rows or columns just reverses the signs. I read somewhere, probably in connections with holographic algorithms introduced by Valiant, that Gaussian elimination could be explained in terms of group action and this in turns leads to generic techniques in complexity reduction.

Also, i feel that almost all source of complexity reduction for any computational problem is some sort of symmetry present. Is it true? Can we rigorously formalize this in terms of group theory?

Edit

I found the reference. (pg 2, last line of second paragraph). I did not understand the paper properly, If my question is based on wrong understanding of the paper, please correct me.

$\endgroup$
  • 3
    $\begingroup$ My personal take on the second paragraph: Problems of wide interest often have symmetry, whether they have efficient algorithms or not. But other than that, I do not see the truth in your feeling that “almost all source of complexity reduction for any computational problem is some sort of symmetry present.” For example, I fail to see what symmetry Kruskal’s algorithm uses. Moreover, the view that efficient algorithms arise from symmetry in problems does not seem to explain why the symmetry of the permanent apparently does not help computing it efficiently. $\endgroup$ – Tsuyoshi Ito Aug 28 '12 at 14:37
  • 4
    $\begingroup$ No, symmetry does not always lower complexity. Every interesting question about groups is undecidable. Sorting is not. $\endgroup$ – Jeffε Aug 28 '12 at 14:37
  • 2
    $\begingroup$ the closest formal statement in this direction that comes to mind is the algebraic dichotomy conjecture, which (to put it very vaguely) states that a CSP is in P if and only if there are nontrivial ways to combine two solutions into a genuinely different third solution. one example is solving a linear system mod 2, which is solvable by gaussian elimination, and where two different solutions determine an affine subspace of solutions $\endgroup$ – Sasho Nikolov Aug 28 '12 at 17:40
  • 2
    $\begingroup$ ah so what you're actually talking about is GCT, which starts from the idea that the permanent vs. determinant problem can be understood in terms of (roughly) the symmetries under which the two functions are invariant. $\endgroup$ – Sasho Nikolov Aug 29 '12 at 18:37
  • 2
    $\begingroup$ There are lots of reasons why a problem admits an efficient algorithm. Convexity, sub-modularity, etc. Symmetries cause case explosion in some combinatorial problems and are sometimes viewed as a source of inefficiency. $\endgroup$ – Vijay D Aug 29 '12 at 23:56
12
$\begingroup$

In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) and is characterized by that symmetry group (meaning any other homogeneous degree $n$ polynomial in $n^2$ variables with those symmetries must be a scalar multiple of the determinant). (And, as to @Tsuyoshi Ito's point that the symmetries of the permanent seem not to help compute it efficiently: although the permanent is also characterized by its symmetries, its symmetry group is much smaller than that of the determinant.)

You can find a write-up of this - where the symmetries of the determinant are used to do Gaussian elimination, along the way proving that the determinant is characterized by its symmetries - in Proposition 3.4.3 of my thesis (shameless self plug - but also, I've never seen it phrased quite this way before and written in full detail, as the OP was asking for, though I'm sure it's been done; I'd be happy if someone had other references).

As to the idea that symmetry always leads to complexity reduction (or not), in addition to things already in the comments, see this question and its answers.

An interesting point is that in Valiant's first papers on what is now known as Valiant's version of algebraic complexity theory, he was trying to make the point that one reason the determinant is important computationally is because roughly all the (then) known efficient algorithms could be reduced to linear algebra and thence to the computation of the determinant, e.g. the FKT algorithm for counting matchings in planar graphs. This is of course an exaggeration, but continues to be borne out by research into holographic algorithms, which often reduce to computing the Pfaffian (a close relative of the determinant). Surely Valiant knew this was an exaggeration, but here's the exact quote just to make sure I'm not misrepresenting (L. Valiant. Completeness classes in algebra. ACM STOC 1979):

Our main conclusions can be summarized roughly as follows:

(a) Linear algebra offers essentially the only fast technique for computing multivariate polynomials of moderate degree

(b) ...

$\endgroup$
7
$\begingroup$

There are cases where the symmetries of a problem ( seem to ) characterize its complexity. One very interesting example is constraint satisfaction problems (CSPs).

Definition of CSP

A CSP is given by a domain $U$, and a constraint language $\Gamma$ ($k$-ary functions from $U^k$ to $\{0, 1\}$). A constraint satisfaction instance is given by a set of variables $V$ and constraints from $\Gamma$. A solution to the instance is an assignment $\phi:V \rightarrow U$ such that all constraints are satisfied.

For example, in this language 3-SAT is given by $\Gamma$ which is the set of all disjunctions of 3 literals, $U$ is simply $\{0, 1\}$. For another example, systems of linear equations mod 2 are given by a $\Gamma$ which is all linear equations mod 2 with $k$ variables, and $U$ is again $\{0, 1\}$.

Polymorphisms

There is a sense in which the hardness of a CSP is characterized by its symmetries. The symmetries in question are called polymorphisms. A polymorphism is a way to locally combine several solutions to a CSP to get a new solution. Locally here means that there is a function that is applied to each variable separately. More precisely, if you have several solutions (satisfying assignments) $\phi_1, \ldots, \phi_t$, a polymorphism is a function $f:U^t \rightarrow U$ that can be applied to each variable to get a new solution $\phi$: $\phi(v) = f(\phi_1(v), \ldots, \phi_t(v))$. For $f$ to be a polymorphism it should map all tuples of $t$ satisfying assignments to any instance to a satisfying assignment of the same instance.

A polymorphism for systems of linear equations for example is $f(x, y, z) = x + y + z \pmod 2$. Notice that $f(x, x, y) = f(y, x, x) = y$. An $f$ that satisfies this property is known as a Maltsev operation. CSPs that have a Maltsev polymorphism are solvable by Gaussian elimination.

On the other hand, disjunctions of 3 literals only have dictators as polymorphisms, i.e. functions of the type $f(x, y) = x$.

Polymorphisms and Complexity (the dichotomy conjecture)

Polymorphisms in fact have computational implications: if a CSP $\Gamma_1$ admits all polymorphisms of $\Gamma_2$, then $\Gamma_1$ is polynomial-time reducible to $\Gamma_2$. This is a way to formally say that a CSP $\Gamma_2$ which is "less symmetric" than another CSP $\Gamma_1$ is in fact harder.

A major open problem in complexity theory is to characterize the hardness of CSPs. The dichotomy conjecture of Feder and Vardi states that any CSP is either in P or NP-complete. The conjecture can be reduced to a statement about polymorphisms: a CSP is NP-hard if and only if the only polymorphisms it admits are "dictators" (otherwise it is in P). I.e. a CSP is hard only if there is no local way to form genuine new solutions from old solutions. The if part (hardness) is known, but the only if part (designing a polytime algorithm) is open.

However, an important case where we do have a dichotomy is boolean CSPs (where $U = \{0, 1\}$). According to Schaefer's theorem, a boolean CSP is in P if it admits one of 6 polymorphisms, otherwise it is NP-complete. The six polymorphisms are basically what you need to solve the problem either by gaussian elimination or by propagation (as you do with horn-sat for example), or to solve it by a trivial assignment.

To read more about polymorphisms, universal algebra, and the dichotomy conjecture, you can look at the survey by Bulatov.

Polymorphisms and Approximability

I also recommend an IAS lecture by Prasad Raghavendra where he puts his result giving optimal approximability of any CSP assuming the unique games conjecture in a similar framework. On a high level, if all polymorphisms (this needs to be generalized to handle approximation problems) of a CSP are close to dictators, one can use the CSP to design a way to test if a function is a dictator, and that turns out to be all you need in order to give a hardness of approximation reduction from unique games. This gives the hardness direction of his result; the algorithmic direction is that when a CSP has a polymorphism which is far from a dictator, one can use an invariance principle (generalization of central limit theorems) to argue that an SDP rounding algorithm gives a good approximation. A really sketchy intuition for the algorithmic part: a polymorphism that is far from a dictator doesn't care if it is given as arguments (a distribution over) variable assignments or gaussian random variables that locally approximate a distribution over variable assignments. This is the same way that a sum function "doesn't care" if it is given discrete random variables with small variance or gaussian r.v.'s with the same variance, by the central limit theorem. The gaussian random variables we need can be computed from an SDP relaxation of the CSP problem. So we find a polymorphism that is far from a dictator, feed it the gaussian samples, and get a good solution back.

$\endgroup$
  • 2
    $\begingroup$ Bulatov also gave an invited talk about his survey at CSR 2011. $\endgroup$ – Tyson Williams Aug 30 '12 at 15:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.