EUVIMEDEUVIMED entdecken
Crossref

Solvable Group Isomorphism Is (Almost) in NP ∩ coNP

Vikraman Arvind, Jacobo Torán

ACM Transactions on Computation Theory · 2011

DOI: 10.1145/1944857.1944859 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2011. Verfasst von Vikraman Arvind und 1 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 23 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Group Isomorphism problem consists in deciding whether two input groups G 1 and G 2 given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group Nonisomorphism problem such that on input groups ( G 1 , G 2 ) of size n , Arthur uses O (log 6 n ) random bits and Merlin uses O (log 2 n ) nondeterministic bits. We derandomize this protocol for the case of solvable groups showing the following two results: (a) We give a uniform NP machine for solvable Group Nonisomorphism, that works correctly on all but 2log O (1)( n ) inputs of any length n . Furthermore, this NP machine is always correct when the input groups are nonisomorphic. The NP machine is obtained by an unconditional derandomization of the aforesaid AM protocol. (b) Under the assumption that EXP \not\subseteq i.o--PSPACE we get a complete derandomization of the aforesaid AM protocol. Thus, EXP \not\subseteq i.o--PSPACE implies that Group Isomorphism for solvable groups is in NP ∩ coNP.

Zitieren

APA

Arvind, V., & Torán, J. (2011). Solvable Group Isomorphism Is (Almost) in NP ∩ coNP. ACM Transactions on Computation Theory. https://doi.org/10.1145/1944857.1944859

Vancouver

Arvind V, Torán J. Solvable Group Isomorphism Is (Almost) in NP ∩ coNP. ACM Transactions on Computation Theory. 2011. doi:10.1145/1944857.1944859

BibTeX
@article{Arvind2011,
  author = {Arvind, Vikraman and Torán, Jacobo},
  title = {Solvable Group Isomorphism Is (Almost) in NP ∩ coNP},
  journal = {ACM Transactions on Computation Theory},
  year = {2011},
  doi = {10.1145/1944857.1944859}
}
Kostenlos starten →