An important problem in computational complexity.
String
\(S\): a set.
\(A\): an alphabet. Yet another set.
\(\sigma : S \rightarrow A\): a string. Map from \(S\) to \(A\).
\(p:S \leftrightarrow S\): a bijection from \(S\) to \(S\).
\({Sym}_S = \{ p \}\): group of all permutations of \(S\). Symmetric group.
\(G\): subgroup of \({Sym}_S\).
String Isomorphism
\(\sigma_1\): string.
\(\sigma_2\): string.
\(G\): subgroup of \({Sym}_S\).
Question
Is there some \(p \in G\) such that \(p(\sigma_1) = \sigma_2\) ?