Laboratory of Mathematical Logic at PDMI

Пятница, 13 июня, ауд. 203. Начало в 12:00.

Докладчик: Volker Diekert (University of Stuttgart , Germany).

Тема: Conjugacy in Baumslag's group, generic case complexity, and division in power circuits.

Abstract

In my talk I report about a recent joint work with Alexei Myasnikov and Armin Weiss which was presented at the conference LATIN 2014 in Montevideo. The motivation stems from algorithmic group theory. It concerns the conjugacy problem for two prominent groups: the Baumslag-Solitar group BS(1,2) and the Baumslag's group BG(1,2). The groups are quite different although the second one, B(1,2) is still a one-relator group and obtained by a single HNN extension of the Baumslag-Solitar group BS(1,2) The word problem and the conjugacy problem in the Baumslag-Solitar group is easy, but this does not transfer to BG(1,2).

Our main result shows that conjugacy in BG(1,2) can be solved in polynomial time in a strongly generic setting. The result is surprising because our algorithm has non-elementary average case complexity; and we conjecture that this is the best we can expect. This is interesting in a broader sense since it relates a natural conjugacy problem in algorithmic group theory to integer division in power circuits. A power circuit is a data structure which allows to represent huge numbers involving tower functions by small graphs. Actually, the complexity of the division problem in power circuits is an open and interesting problem in arithmetic.