Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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-hard $ ie. harder then NP-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?

share|improve this question
    
Crossposted from cstheory.stackexchange.com/questions/12422/… . –  Emil Jeřábek Aug 28 '12 at 13:22
    
@Emil I did not get answer there.. so I posted here as well. Should I remove one of the questions? Which one? –  DurgaDatta Aug 28 '12 at 14:14
1  
Simultaneous cross-posting is generally not welcome, as it fragments the discussion and makes people duplicate the effort. It makes sense to reask the question on another forum if you do not get an answer, but you should wait at least a couple of days, not 3 hours, especially on a relatively low-traffic site like cstheory.SE. In any case, you should link the two questions to each other so that people are aware of it (as I did above). I don’t think it’s necessary to remove the question, but please keep this in mind for the future. –  Emil Jeřábek Aug 28 '12 at 14:30
    
You mean the left action by multiplication of the group of lower-triangular unipotent matrices? –  Will Sawin Aug 28 '12 at 14:55
    
Thank you @Emil. I will keep that in mind. –  DurgaDatta Aug 28 '12 at 15:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.