Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUBGROUP DISTANCE PROBLEM:
Reports tagged with Subgroup Distance problem:
TR06-146 | 30th September 2006
Christoph Buchheim, Peter J Cameron, Taoyang Wu

On the Subgroup Distance Problem

We investigate the computational complexity of finding an element of
a permutation group~$H\subseteq S_n$ with a minimal distance to a
given~$\pi\in S_n$, for different metrics on~$S_n$. We assume
that~$H$ is given by a set of generators, such that the problem
cannot be solved in polynomial time ... more >>>




ISSN 1433-8092 | Imprint