Parallel algorithms for power circuits and the word problem of the Baumslag group

Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Won as a data structure for non-elementarily compressed integers supporting the arithmetic operations addition and ( x , y ) ↦ x · 2 y . The same authors applied power circuits to give a polynomial time solution to the word proble...

Full description

Saved in:
Bibliographic Details
Published in:Computational complexity 2023-12, Vol.32 (2), Article 10
Main Authors: Mattes, Caroline, Weiß, Armin
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Circuits
Computational Mathematics and Numerical Analysis
Computer Science
Data structures
Integers
Polynomials
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Won as a data structure for non-elementarily compressed integers supporting the arithmetic operations addition and ( x , y ) ↦ x · 2 y . The same authors applied power circuits to give a polynomial time solution to the word problem of the Baumslag group, which has a non-elementary Dehn function. In this work, we examine power circuits and the word problem of the Baumslag group under parallel complexity aspects. In particular, we establish that the word problem of the Baumslag group can be solved in NC — even though one of the essential steps is to compare two integers given by power circuits and this, in general, is shown to be P -complete. The key observation is that the depth of the occurring power circuits is logarithmic and such power circuits can be compared in NC .
ISSN:1016-3328
1420-8954
DOI:10.1007/s00037-023-00244-x