<p>As for what invariant properties are being used, and what transformations are being applied to the permanent and determinant, see the <a href="https://cstheory.stackexchange.com/questions/170/how-does-the-mulmuley-sohoni-geometric-approach-to-producing-lower-bounds-avoid-p/186#186">answer</a> to a related question.</p>

<p>As for how the symmetry is used to explain computational hardness: it's not. First, it's not just symmetry that is being used, but <em>characterization by symmetries</em>.  As discussed in <a href="https://cstheory.stackexchange.com/questions/871/relationship-between-symmetry-and-computational-intractability">another question of yours</a>, symmetry can very well make a function <em>easier</em> to compute. </p>

<p>Second, even characterization by symmetries does not explain hardness - since both $det$ and $perm$ are characterized by their symmetries, but $det$ is easy. The idea instead is this: it should be easier to understand the algebro-geometric and representation-theoretic properties of functions that are characterized by their symmetries, and hence to carry out the GCT plan of attack.</p>

<p>Since most functions are not characterized by their symmetries, using characterization by symmetries in a crucial way also gives some hope of bypassing the natural proofs barrier, <a href="https://cstheory.stackexchange.com/questions/170/how-does-the-mulmuley-sohoni-geometric-approach-to-producing-lower-bounds-avoid-p">as discussed here</a>.</p>

<p>(That characterization by symmetries should make understanding easier can be formalized a  tiny bit more as follows. Since GCT is studying the orbits of $det$ and $perm$, and there is a sort of duality between orbits and stabilizers, functions that are characterized by their stabilizers should have "special" orbits in some sense. I guess this alone doesn't actually say anything about how difficult it should be to understand these orbits. But understanding "generic" orbits can be very hard; having a nice property like characterization by symmetries at least gives us something to grab on to that we can try to use to gain more understanding.)</p>

CC BY-SA 2.5
2010-10-05T15:38:50.780Z
2010-10-05T17:01:35.713Z
2017-04-13T12:32:28.743Z
Joshua Grochow
<p>I'm not well versed in geometric complexity theory so my question could be trivial. I understand that GCT program  studies the symmetries of determinant and permanent to prove Valiant's Hypothesis: $VP\ne VNP$</p>

<blockquote>
  <p>In simple terms, What is the invariant property? Which mapping (transformation) is applied to the determinant and permanent? How is the symmetry of permanent used to explain the difficulty of computing the permanent?</p>
</blockquote>

CC BY-SA 2.5
2010-10-04T17:23:51.890Z
You may consult the following: http://math-www.uni-paderborn.de/agpb/vortrag/ow09-mytalk.pdf and http://www.cse.iitk.ac.in/users/manindra/survey/Determinant.pdf.
Sadeq Dousti
CC BY-SA 2.5
2010-10-04T17:38:35.403Z
@Sadeq, thanks for the pointers. I did not find direct answers to my questions.
Mohammad Al-Turkistany
<cc.complexity-theory><gct><symmetry>
The role of symmetry in geometric complexity theory?
Mohammad Al-Turkistany
# The role of symmetry in geometric complexity theory?

(Asked by: username_0 on 2010-10-04)

I'm not well versed in geometric complexity theory so my question could be trivial. I understand that GCT program studies the symmetries of determinant and permanent to prove Valiant's Hypothesis: $VP\ne VNP$

> In simple terms, What is the invariant property? Which mapping (transformation) is applied to the determinant and permanent? How is the symmetry of permanent used to explain the difficulty of computing the permanent?

**Tags:** cc.complexity-theory, gct, symmetry

> **Comments:**
> **username_1**: You may consult the following: http://math-www.uni-paderborn.de/agpb/vortrag/ow09-mytalk.pdf and http://www.cse.iitk.ac.in/users/manindra/survey/Determinant.pdf.  
> **username_0**: @Sadeq, thanks for the pointers. I did not find direct answers to my questions.  

---

## 1 answers

### Answer by username_2 on 2010-10-05. Score: 6 | Accepted answer

As for what invariant properties are being used, and what transformations are being applied to the permanent and determinant, see the [answer](https://cstheory.stackexchange.com/questions/170/how-does-the-mulmuley-sohoni-geometric-approach-to-producing-lower-bounds-avoid-p/186#186) to a related question.

As for how the symmetry is used to explain computational hardness: it's not. First, it's not just symmetry that is being used, but *characterization by symmetries*. As discussed in [another question of yours](https://cstheory.stackexchange.com/questions/871/relationship-between-symmetry-and-computational-intractability), symmetry can very well make a function *easier* to compute.

Second, even characterization by symmetries does not explain hardness - since both $det$ and $perm$ are characterized by their symmetries, but $det$ is easy. The idea instead is this: it should be easier to understand the algebro-geometric and representation-theoretic properties of functions that are characterized by their symmetries, and hence to carry out the GCT plan of attack.

Since most functions are not characterized by their symmetries, using characterization by symmetries in a crucial way also gives some hope of bypassing the natural proofs barrier, [as discussed here](https://cstheory.stackexchange.com/questions/170/how-does-the-mulmuley-sohoni-geometric-approach-to-producing-lower-bounds-avoid-p).

(That characterization by symmetries should make understanding easier can be formalized a tiny bit more as follows. Since GCT is studying the orbits of $det$ and $perm$, and there is a sort of duality between orbits and stabilizers, functions that are characterized by their stabilizers should have "special" orbits in some sense. I guess this alone doesn't actually say anything about how difficult it should be to understand these orbits. But understanding "generic" orbits can be very hard; having a nice property like characterization by symmetries at least gives us something to grab on to that we can try to use to gain more understanding.)


---

