caa a22 4500 469033924 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920901xx s 000 0 eng 10.1007/BF01272075 doi (NATIONALLICENCE)springer-10.1007/BF01272075 Rónyai Lajos Computer and Automation Institute, Hungarian Academy of Sciences, Victor Hugo u. 18-22, H-1132, Budapest, HUNGARY aut Algorithmic properties of maximal orders in simple algebras over Q [Elektronische Daten] [Lajos Rónyai] This paper addresses an algorithmic problem related to associative algebras. We show that the problem of deciding if the index of a given central simple algebra $$\mathcal{A}$$ over an algebraic number field isd, whered is a given natural number, belongs to the complexity classN P ∩co N P. As consequences, we obtain that the problem of deciding if $$\mathcal{A}$$ is isomorphic to a full matrix algebra over the ground field and the problem of deciding if $$\mathcal{A}$$ is a skewfield both belong toN P ∩co N P. These results answer two questions raised in [25]. The algorithms and proofs rely mostly on the theory of maximal orders over number fields, a noncommutative generalization of algebraic number theory. Our results include an extension to the noncommutative case of an algorithm given by Huang for computing the factorization of rational primes in number fields and of a method of Zassenhaus for testing local maximality of orders in number fields. Birkhäuser Verlag, 1992 68Q40 nationallicence 11Y40 nationallicence 68Q25 nationallicence 11Y16 nationallicence computational complexity Birkhäuser-Verlag 2/3(1992-09-01), 225-243 1016-3328 2:3<225 1992 2 37 https://doi.org/10.1007/BF01272075 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01272075 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Rónyai Lajos Computer and Automation Institute, Hungarian Academy of Sciences, Victor Hugo u. 18-22, H-1132, Budapest, HUNGARY aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/3(1992-09-01), 225-243 1016-3328 2:3<225 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer