Algorithmic theory of free solvable groups: randomized computations.

DOI10.1016/J.JALGEBRA.2014.02.014zbMATH Open1336.20038arXiv1407.1691OpenAlexW2087202152MaRDI QIDQ402669FDOQ402669

Authors: Alexander Ushakov 

Publication date: 28 August 2014

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

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.

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

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.

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)

Cites Work

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

Cited In (10)

• Efficient computations with counting functions on free groups and free monoids
• An analysis of Makanin's algorithm deciding solvability of equations in free groups
• Algorithmic theory of solvable groups
• Title not available (Why is that?)
• The word and geodesic problems in free solvable groups.
• Title not available (Why is that?)
• Algorithmic problems for free-Abelian times free groups.
• Title not available (Why is that?)
• Spherical quadratic equations in free metabelian groups.
• Magnus embedding and algorithmic properties of groups \(F/N^{(d)}\)

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)