HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Is Group Theory useful in Computer Science in areas other than cryptography?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#127978, answer score: 21

Revisions (0)

No revisions yet.