Algorithmic theory of free solvable groups: randomized computations.

DOI10.1016/J.JALGEBRA.2014.02.014MaRDI QIDQ402669zbMATH OpenOpenAlexFDO

Authors Alexander Ushakov

Publication date 28 August 2014

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.1691

zbMATH Keywords

randomized algorithmsconjugacy problemword problemmetabelian groupscyclic subgroup membership problemfree solvable groupsMonte Carlo type algorithmspower problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Solvable groups, supersolvable groups (20F16)

Abstract: We design new deterministic and randomized algorithms for computational problems in free solvable groups. In particular, we prove that the word problem and the power problem can be solved in quasi-linear time and the conjugacy problem can be solved in quasi-quartic time by Monte Carlo type algorithms.

Recommendations

• The word and geodesic problems in free solvable groups.
• Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. II
• On the complexity of intersection and conjugacy problems in free groups
• Algorithmic theory of solvable groups
• Polynomial-time word problems.

Cites work

• scientific article; zbMATH DE number 3158802 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3394414 (Why is no real title available?)
• A Fast Monte-Carlo Test for Primality
• Combinatorial group theory.
• Fast multiplication of large numbers
• Free differential calculus. I: Derivation in the free group ring. II: The isomerphism problem of groups. III: Subgroups
• Free differential calculus. II: The isomorphism problem of groups
• Free differential calculus. III: Subgroups
• Free differential calculus. V: The Alexander matrices reexamined
• GEOMETRICAL APPROACH TO THE FREE SOLVABLE GROUPS
• On quasilinear-time complexity theory
• PRIMES is in P
• Polynomial time conjugacy in wreath products and free solvable groups.
• Probabilistic algorithm for testing primality
• Stallings foldings and subgroups of free groups
• The Conjugacy Problem in Wreath Products and Free Metabelian Groups
• The Length of Elements in Free Solvable Groups
• The word and geodesic problems in free solvable groups.
• Topology of finite graphs

Cited in

(10)

• Algorithmic problems for free-Abelian times free groups.
• scientific article; zbMATH DE number 1919481 (Why is no real title available?)
• Spherical quadratic equations in free metabelian groups.
• Efficient computations with counting functions on free groups and free monoids
• An analysis of Makanin's algorithm deciding solvability of equations in free groups
• The word and geodesic problems in free solvable groups.
• scientific article; zbMATH DE number 597711 (Why is no real title available?)
• Magnus embedding and algorithmic properties of groups \(F/N^{(d)}\)
• scientific article; zbMATH DE number 2144700 (Why is no real title available?)
• Algorithmic theory of solvable groups

This page was built for publication: Algorithmic theory of free solvable groups: randomized computations.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q402669)