patternMajor
Is Group Theory useful in Computer Science in areas other than cryptography?
Viewed 0 times
sciencegrouptheorythancomputerusefulareasothercryptography
Problem
I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot find out where and how to apply Group Theory to other areas in CS, such as algorithms, data structres, graphs, complexity and so forth.
Solution
Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory.
An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with groups.
An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with groups.
Context
StackExchange Computer Science Q#127978, answer score: 21
Revisions (0)
No revisions yet.