¿Es el isomorfismo del grupo abeliano en

Es fácil ver un algoritmo de tiempo de ejecución para el isomorfismo de grupo abeliano. Más tarde, trabajando en este problema en 2003, Vikas mejoró el resultado del tiempo de ejecución de a . En 2007, Kavitha demostró que el isomorfismo del grupo abeliano se puede hacer en tiempo lineal, es decir, tiempo . $O(n^2)$ $O(n^2)$ $O(n \log n)$ $O(n)$

Sé que el isomorfismo de grupo abeliano cuando los grupos se dan por representación de tabla está en . ¿Hay algún trabajo de investigación o artículo que muestre que está en ? Traté de google pero solo obtuve el resultado de que está en . $\mathsf{TC^0}$ $\mathsf{AC^0}$ $\mathsf{TC^0}$

Pregunta: ¿Es el isomorfismo de grupo abeliano (grupos dados en representación de tabla) en $\mathsf{AC^0}$

cc.complexity-theory ds.algorithms nuevo
fuente

pregunta en cs, cs.stackexchange.com/questions/87369/is-finite-abelian-group-isomorphism-in-log-space - el resultado muestra un subgrupo abeliano en

;

L

$L$

T C^{0} (F O L L)

$TC^{0}(FOLL)$

user3483902

Ya hizo una pregunta similar en CS.SE ( cs.stackexchange.com/q/87369/755 ) y ya recibió una respuesta allí que proporciona una cita a un documento que considera este problema. ¿Por qué no mencionó que ya había recibido una respuesta y citó ese documento? ¿Has intentado hacer una búsqueda en la literatura a partir de ese documento, para buscar otros documentos que lo citan o que cita para ver si hay algo en la literatura sobre el tema? Debería hacer una búsqueda de literatura por su cuenta antes de preguntar ... y debería resumir otras respuestas que ya haya recibido.

Hubiera sido mejor (a) citar el artículo, y (b) hacer la búsqueda de literatura que sugiero, y (c) informar sobre los resultados de la búsqueda de literatura en la pregunta. No mencionas si hiciste la búsqueda de literatura. Si ha realizado la búsqueda bibliográfica y no ha encontrado nada, tal vez no se sepa.

En realidad, una referencia para el reclamo TC ^ 0 sería bueno.

Emil Jeřábek

No se sabe que está en TC0. Por lo tanto, no se sabe que esté en AC0.

Jane

Respuestas:

Al contrario de lo que se afirma en la pregunta, no se sabe que el isomorfismo del grupo abeliano esté en . No hace falta decir que esto también significa que no se sabe que está en . $\mathrm{TC^0}$ $\mathrm{AC^0}$

$\mathrm{pow}$ $(A,{\cdot})$ $a,b\in A$ $m$ $b=a^m$ $A,B$ $n$

\begin{matrix} (*) & A ≃ B ⟺ \forall m \leq n | {a \in A : a^{m} = 1} | = | {b \in B : b^{m} = 1} | . \end{matrix}

$\tag{$*$}A\simeq B\iff\forall m\le n\:\bigl|\{a\in A:a^m=1\}\bigr|=\bigl|\{b\in B:b^m=1\}\bigr|.$

$\mathrm{TC^0}$

$\mathrm{TC^0(pow)}$

$\mathrm{pow}$

$\mathrm{L}$ $\mathrm{TC^0(FOLL)}$

$\mathrm{pow}$ $\mathrm{TC^0}$

$\mathrm{AC^0}$

$\Sigma_2\text-\mathrm{TIME}\bigl((\log n)^2\bigr)$

$2^{O((\log n)^2)}$ $O\bigl((\log n)^2\bigr)$ $2\frac12$

$O(\log n)$ $A$ $B$ $|A|=|B|=n$ $A\simeq B$

allí existe

$\{m_i:i<k\}$ $k\le\log n$ $m_i\le n$

$\{a_i:i<k\}\subseteq A$ $\{b_i:i<k\}\subseteq B$

tal que

$\prod_{i<k}m_i=n$

$a_i^{m_i}=1$ $b_i^{m_i}=1$ $i<k$

$\{r_i:i<k\}$ $0\le r_i<m_i$

$\prod_{i<k}a_i^{r_i}\ne1$ $\prod_{i<k}b_i^{r_i}\ne 1$

$\prod_{i<k}a_i^{r_i}=1$ $\mathrm{NTIME}\bigl((\log n)^2\bigr)$ $\prod_{i<l}a_i^{r_i}$ $l=0,\dots,k$ $i$ $O(\log r_i)$ $a_i^{r_i}$ $O\left(\sum_i\log r_i\right)\subseteq O\left(\sum_i\log m_i\right)\subseteq O(\log n)$ $O(\log n)$

$(*)$ $m$ $m=p^e$ $p$ $p$ $\mathrm{AC^0}$ $\mathrm{pow}$ $\mathrm{AC^0}$

$\mathrm{AC^0}$ $m\ll n$ $\mathrm{AC^0}$

Referencias

$\mathrm{AC^0}$

[2] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: Sobre la complejidad de algunos problemas en la entrada de grupos como tablas de multiplicación , Journal of Computer and System Sciences 63 (2001), no. 2, págs. 186–200, doi: 10.1006 / jcss.2001.1764 .

Emil Jeřábek
fuente

Relacionado (y muy reciente): arxiv.org/abs/1802.00659

Joshua Grochow