5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

As for what invariant properties are being used, and what transformations are being applied to the permanent and determinant, see the answer 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, 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.

(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.)

$\endgroup$

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.