# Tag Info

16

It really makes a difference what the input to the algorithm is: how do you specify a group? If you want groups given by generators and relators, I would suggest Combinatorial Group Theory, by Magnus, Karrass, and Solitar (but algorithms there are sparse because too many of the important problems are undecidable). If you want automatic groups (groups whose ...

15

$p$-groups of class 2 and exponent $p$ are widely believed to be the hardest case of Group Isomorphism ($p > 2$). (For $p=2$, we need to consider exponent 4, since all groups of exponent 2 are abelian - easy exercise for the reader.) Although there is as yet no reduction from general GpIso to this class of groups (though see point 0.5 below), there are ...

12

The order of permutation groups can be computed in polynomial-time. In fact, I believe even in $\mathsf{NC}$ and also nearly linear Las Vegas time. See, e.g., the book by Seress. For reference, subgroups of $S_n$ (and algorithms related thereto) are typically called "permutation groups" rather than merely "subgroups (of $S_n$)". So you can google "...

12

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-complete language has a poly-time group action with few orbits, PH collapses. For, with this additional assumption about sampleability, the standard $\mathsf{coAM}$ ...

11

Moderately exponential time and $\mathsf{coAM}$ (for the opposite of the problem as stated: Coset Intersection is typically considered to have a "yes" answer if the cosets intersect, opposite of how it's stated in the OQ.) Luks 1999 (free author's copy) gave a $2^{O(n)}$-time algorithm, while Babai (see his 1983 Ph.D. thesis, also Babai-Kantor-Luks FOCS ...

9

Consider the complement, i.e. where you are asked to test whether $G \pi \cap H \not= \emptyset$. As I pointed out in this answer, testing whether $g \in \langle g_1, \ldots, g_k\rangle$ is in $\text{NC} \subseteq \text{P}$ [1]. So you can guess $g, h \in S_n$ and test in polynomial time whether $g \in G$, $h \in H$ and $g \pi = h$. This yields an $\text{NP}$...

9

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-bound for the $3$-regular case. Maybe there are results in this line for general $k$-regular graphs. For a lower bound, consider formula $F$ with $n$ inputs ...

9

As a complement to Joshua Grochow's answer: Computing the order of a permutation group given generators is in P by Schreier–Sims algorithm, see also p. 8-9 of these lectures notes by Luks. Just as membership in permutation groups, the problem was believed to be P-complete by many researchers, but it was finally shown to be in NC by Babai, Luks & Seress. ...

8

Certainly there has been tons of progress! (And if you really meant to ask about the last 50 years, then that includes the algorithms of Schreier-Sims and Butler that you already mentioned...) For example, see Seress's book [1], which includes many algorithms that upgrade standard tasks into $\mathsf{NC}$ and/or quasi-linear (sometimes Las Vegas) time, such ...

8

One family of results not mentioned in the excellent references of @Marzio's answer is relations between the isoperimetric (Dehn) function of a group $G$ and the nondeterministic time complexity of the word problem in $G$. For example: For finitely generated groups $G$, $WP(G) \in \mathsf{NP}$ if and only if $G$ can be embedded in a finitely presented group ...

8

Maybe this is along the lines you are looking for: I wrote a blog post here explaining how you can use Gromov's theorem on groups of polynomial growth to show that non-uniform read once automata are no more powerful than linear time Turing machines for deciding word problems of groups. The basic idea is that groups with non-uniform read once automata ...

7

There has been some recent work in terms of characterizing automorphism groups of strongly regular graphs using asymptotic group theory (e.g. this paper), which (for many reasons) is likely very closely related to the complexity of algorithms on strongly regular graphs that use group-theoretic methods, although exploiting such properties algorithmically is ...

7

Yes, they can. Recall that any reversible classical function can be computed in superposition. Now, generate the state $$\frac{1}{\sqrt{n!}}\left(\sum_{i=1}^n |i \rangle \right) \left( \sum_{i=1}^{n-1} |i \rangle \right)\left(\sum_{i=1}^{n-2} |i\rangle \right) \ldots \left(\sum_{i=1}^2 |i\rangle \right) \bigg(| 1\rangle \bigg) .$$ This is the ...

7

The answer is yes, we can improve the upper bound to $\mathrm{e}^{(1 + o(1))\sqrt{n\ln n}}$. It was proved in a more recent paper of Babai (Corollary 2.9).

7

I think that you can start (and probably end, because it's a huge list :-) with the references in the recent Charles F. Miller's paper: "Turing machines to word problems" (2013). And another recent paper that surveys the connections between group theory and theory of automata and formal languages and hase a huge (>100 entries) reference section is: Tullio ...

6

The representation theory of the symmetric group plays a key role in the Geometric Complexity Theory approach to lower bounds on the determinant or on matrix multiplication. Bürgisser and Ikenmeyer prove a lower bound on the border-rank of matrix multiplication using the representation theory of $S_n$. For how the representation theory of $S_n$ relates to ...

6

I think this is not known. (I apologize - I think I was also one of the people that said I had remembered reading this somewhere.) For example, I believe that Sapir-Birget-Rips, Annals of Math 2002 were the first to show the existence of a group with $\mathsf{NP}$-complete word problem (which would be a trivial consequence of the result asked for in this ...

6

Yes, the best known algorithm is still the algorithm from Babai and Luks, with runtime $\exp(O(\sqrt{n \log n}))$, where $n$ is the number of vertices in the graphs. Unless I'm mistaken, even the best known conondeterministic algorithm for graph isomorphism has exponential runtime. Babai and Luks' algorithm is plausibly near-optimal for deterministic ...

6

(1) In terms of structural complexity classes (as opposed to just upper bounds on deterministic time), for general Group Isomorphism, the known upper bounds are essentially the same as for Graph Isomorphism, namely $\mathsf{coAM} \cap \mathsf{SZK}$. However, Arvind and Toran showed that Solvable Group Isomorphism is in $\mathsf{NP} \cap \mathsf{coNP}$ under ...

6

The most modern and comprehensive reference is probably "Handbook of Computational Group Theory" by Holt, Eick and O'Brien (link) A classic reference is "Computation in Finitely Presented Groups" by Charles Simms.

6

If you're interested in the group theory that's relevant for Graph Isomorphism, then in addition to Seress's book that David Eppstein mentioned, I would highly recommend Dixon and Mortimer's Permutation Groups The above is a book on "just" group theory, but of the books on pure group theory, it is probably the most relevant to Graph Isomorphism. A book ...

6

Sadly, group structure is nearly so limited that there isn't much one can do with it to be of use in information theory, thus the literature is prone to be fairly sparse. Even Abelian groups aren't enough structure. Even basic abstract algebra texts which have some basic coding theory applications generally provide examples using field theory or linear ...

6

Yes, this can be solved in polynomial time (and, I think, even in $\mathsf{NC}$). First, it's easy to reduce to the case of transitive $G$. Next, find the minimal blocks of $G$. (See e.g. Section 3.6(B) of Dixon & Mortimer.) This can be done by choosing a point $x \in [n]$, and for each $y \in [n]$, $y \neq x$, computing the (undirected) connected ...

5

If you allow the graphs to be disconnected, then there are no good upper bounds, with respect to the number of vertices. For $r$-regular graphs take the disjoint union of $l$ complete graphs $K_{r+1}$. Then the graph has $(r+1)\cdot l$ vertices, and $(r+1)!\cdot l!$ automorphisms.

5

A quantum Fourier transform is a unitary operation, so the number of basis states of the input and output must be the same. The number of basis states before the Fourier transform is 120, the number of group elements. The number of basis states after the Fourier transform is 120, in this case broken up according to the identity  120=1^2+1^2+4^2+4^2+5^2+...

5

This problem is NP-hard. Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world looks, finding the lexicographically least isomorphic string is NP-hard. This is precisely the content of Proposition 3.1 here. In fact, they show it remains NP-...

5

This problem is $FP^{NP}$-complete, as shown here. It means that the lexicographical leader of the orbit is built in deterministic polynomial time with access to a $NP$-oracle.

5

My intuition is that an NP-complete language of this type would cause a collapse of the polynomial hierarchy much like the one in the Karp–Lipton theorem. More specifically, if you go up to the second level of the polynomial hierarchy, you can use the power of the hierarchy to guess the equivalence between a given group element and some representative of an ...

5

Andrew(the asker) and I had discussed this over email, and we have shown the conjecture is false. The polytope is not integral for Abelian groups, not even for cyclic groups. On the positive side. Theorem: For cyclic groups with order $p^kq$, where $p$ and $q$ are primes and $k\in \mathbb{N}$, the incidence matrix of elements and subgroups is totally ...

4

This classical post-processing exploits several non-trivial group theoretical properties of Abelian groups. I wrote a didactic explanation of how this classical algorithm works here [1]; other good sources to read about are [2, 3, 4]. So, measuring at the end of the algorithm in the standard basis will give you elements of $H^{*}$ uniformly at random. It is ...

Only top voted, non community-wiki answers of a minimum length are eligible