Speaker
Description
Markus Lohrey and Andreas Rosowski
Abstract: We prove that it is $\Pi_2^{\mathsf{P}}$-complete to verify whether the diameter of a given permutation group $G = \langle A \rangle$ is bounded by a unary encoded number $k$. This solves an open problem from a paper of Even and Goldreich, where the problem was shown to be NP-hard. Verifying whether the diameter is exactly $k$ is complete for the class consisting of all intersections of a $\Pi_2^{\mathsf{P}}$-language and a $\Sigma_2^{\mathsf{P}}$-language. A similar result is shown for the length of a given permutation $\pi$, which is the minimal $k$ such that $\pi$ can be written as a product of at most $k$ generators from $A$. Even and Goldreich proved that it is $\mathsf{NP}$-complete to verify, whether the length of a given $\pi$ is at most $k$ (with $k$ given in unary encoding). We show that it is DP-complete to verify whether the length is exactly $k$.
Finally, we deduce from our result on the diameter that it is $\Pi_2^{\mathsf{P}}$-complete to check whether a given finite automaton with transitions labelled by permutations from $S_n$ produces all permutations from $S_n$.