# Complexity of computing the Galois group

There has been some discussion of computing the Galois group of a polynomial over the integers, but I can't seem to find any results, or even a question of what the complexity of this might be. For example, I assume that this is NOT in NP, and IS NP-hard (at least), but am not aware of any reduction...

• One of my fellow students wrote a bachelor's thesis on computing the size of the Galois group: math.leidenuniv.nl/nl/theses/311 . I realise that the size forgets the whole group structure, but I still thought this might be relevant as comment. – jmc Nov 21 '13 at 8:11
• @jmc I had actually seen this thesis before (thanks to Google), and was quite impressed! Hope your colleague is still in mathematics! – Igor Rivin Nov 21 '13 at 13:47
• Dear Igor Rivin, he definitely is! (Finishing his master's right now, if I am not mistaken.) – jmc Nov 21 '13 at 15:02

This paper gives some complexity bounds on computing the order (they show this is in $P^{\# P}$ see the complexity zoo). Google seems to say there is a paper proving that nilpotence of the Galois group is decidable in polynomial time.
• The Landau in question is Susan Landau, so "her theorem". But anyway, as you say, the size of the Galois group can be (and usually is) $n!$ so this is not a particularly useful bound. Landau and Gary Miller (if memory serves) had a rather complicated algorithm computing solvable Galois groups in polynomial time thirty years ago. I believe they computed the structure, not just the order. I do recall seeing something about nilpotent groups, but in some sense the most interesting case is of [nonabelian] simple groups (which are not $A_n$ -- that can be done in poly time). – Igor Rivin Nov 21 '13 at 13:52