2
$\begingroup$

The below-given problem is in black box setting means input is given by set of generators.

Given an abelian $p$-group $A$ and two matrices $U_1$ and $U_2$ in $R(A)$ such that the order of $U_1$ and $U_2$ are coprime with $p$, output an element $U \in R(A)$ such that $UU_1=U_2U$ if such an element exists.

$R(A)$ denotes the set of all automorphisms of $A$.

The brute force way seems to give a $\Theta(|A|^{\log |A|})$ bound.

Question: Is the above problem solvable in the polynomial time?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.