检索结果-内蒙古大学图书馆

Conjugacy in Baumslag's Group, generic case complexity, and Division in Power Circuits

ALGORITHMICA 2016年第4期76卷 961-988页

作者： Diekert, Volker Myasnikov, Alexei G. Weiss, Armin Univ Stuttgart FMI Univ Str 38 D-70569 Stuttgart Germany Stevens Inst Technol Dept Math Hoboken NJ 07030 USA

The conjugacy problem asks whether two words over generators of a fixed group G are conjugated, i.e., it is the problem to decide on input words x, y whether there exists z such that in G. The conjugacy problem is more difficult than the word problem, in general. We investigate the conjugacy problem for two prominent groups: the Baumslag-Solitar group and the Baumslag group (also known as Baumslag-Gersten group). The conjugacy problem in is complete for the circuit class . To the best of our knowledge is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group is an HNN-extension of . Hence, decidability of the conjugacy problem in outside the so-called "black hole" follows from Borovik et al. (Int J Algebra Comput 17(5/6):963-997, 2007). Decidability everywhere is due to Beese. Moreover, he showed exponential time for the set of elements which cannot be conjugated into (Beese 2012). Here we improve Beese's result in two directions by showing that the conjugacy problem in can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs, conjugacy in can be decided efficiently. In contrast, we show that under a plausible assumption the average case complexity of the same problem is non-elementary. Moreover, we provide a lower bound for the conjugacy problem in by reducing the divisibility problem in power circuits to the conjugacy problem in . The complexity of the divisibility problem in power circuits is an open and interesting problem in integer arithmetic. We conjecture that it cannot be solved in elementary time because we can show that it cannot be solved in elementary time by calculating modulo values in power circuits.

关键词： Algorithmic group theory Power circuit generic case complexity Divisibility problem Conjugacy problem Baumslag group

来源：评论

学校读者我要写书评

暂无评论

Conjugacy in Baumslag's Group, generic case complexity, and Division in Power Circuits

Conjugacy in Baumslag's Group, Generic Case Complexity, and ...

引用

11th Latin American Theoretical INformatics Symposium (LATIN)

作者： Diekert, Volker Myasnikov, Alexei G. Weiss, Armin Univ Stuttgart FMI Univ Str 38 D-70569 Stuttgart Germany Stevens Inst Technol Dept Math Hoboken NJ USA

ISBN: (纸本)9783642544231

The conjugacy problem is the following question: given two words x, y over generators of a fixed group G, decide whether x and y are conjugated, i.e., whether there exists some z such that zxz(-1) = y in G. The conjugacy problem is more difficult than the word problem, in general. We investigate the conjugacy problem for two prominent groups: the Baumslag-Solitar group BS1,2 and the Baumslag(-Gersten) group G(1,2). The conjugacy problem in BS1,2 is TC0-complete. To the best of our knowledge BS1,2 is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group G(1,2) is an HNN-extension of BS1,2 and its conjugacy problem is decidable G(1,2) by a result of Beese (2012). Here we show that conjugacy in G(1,2) can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs conjugacy in G(1,2) can be decided efficiently. In contrast, we show that under a plausible assumption the average case complexity of the same problem is non-elementary. Moreover, we provide a lower bound for the conjugacy problem in G(1,2) by reducing the division problem in power circuits to the conjugacy problem in G(1,2). The complexity of the division problem in power circuits is an open and interesting problem in integer arithmetic.

关键词： Algorithmic group theory power circuit generic case complexity

来源：评论

学校读者我要写书评

暂无评论

Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem

引用

JOURNAL OF SYMBOLIC COMPUTATION 2017年 83卷 147-165页

作者： Diekert, Volker Myasnikov, Alexei G. Weiss, Armin Univ Stuttgart FMI Stuttgart Germany Stevens Inst Technol Hoboken NJ 07030 USA

In various occasions the conjugacy problem in finitely generated amalgamated products and HNN extensions can be decided efficiently for elements which cannot be conjugated into the base groups. Thus, the question arises "how many" such elements there are. This question can be formalized using the notion of strongly generic sets and lower bounds can be proven by applying the theory of amenable graphs. In this work we examine Schreier graphs of amalgamated products and HNN extensions. For an amalgamated product G = H*AK with [H : A] >= [K : A] >= 2, the Schreier graph with respect to H or K turns out to be non-amenable if and only if [H : A] >= 3. Moreover, for an HNN extension of the form G = (H, b vertical bar bab(-1) = phi(a), a is an element of A), we show that the Schreier graph of G with respect to the subgroup H is non-amenable if and only if A not equal H not equal phi(A). As application of these characterizations we show that the conjugacy problem in fundamental groups of finite graphs of groups with finitely generated free abelian vertex groups can be solved in polynomial time on a strongly generic set. Furthermore, the conjugacy problem in groups with more than one end can be solved with a strongly generic algorithm which has essentially the same time complexity as the word problem. These are rather striking results as the word problem might be easy, but the conjugacy problem might be even undecidable. Finally, our results yield a new proof that the set where the conjugacy problem of the Baumslag group G(1,2) is decidable in polynomial time is also strongly generic. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： generic case complexity Amenability Schreier graph HNN extension Amalgamated product Conjugacy problem

来源：评论

学校读者我要写书评

暂无评论

Amenability of Schreier Graphs and Strongly generic Algorithms for the Conjugacy Problem 15

Amenability of Schreier Graphs and Strongly Generic Algorith...

引用

ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Diekert, Volker Myasnikov, Alexei G. Weiss, Armin Univ Stuttgart FMI Stuttgart Germany Stevens Inst Technol Hoboken NJ 07030 USA

ISBN: (纸本)9781450334358

In various occasions the conjugacy problem in finitely generated amalgamated products and HNN extensions can be decided efficiently for elements which cannot be conjugated into the base groups. This observation asks for a bound on how many such elements there are. Such bounds can be derived using the theory of amenable graphs: In this work we examine Schreier graphs of amalgamated products and HNN extensions. For an amalgamated product G = H (*A) K with [H : A] >= [K : A] >= 2, the Schreier graph with respect to H or K turns out to be non-amenable if and only if [H : A] >= 3. Moreover, for an HNN extension of the form G = < H, b vertical bar bab(-1) = phi(a);a is an element of A >, we show that the Schreier graph of G with respect to the subgroup H is non-amenable if and only if A not equal H not equal phi(A). As application of these characterizations we show that under certain conditions the conjugacy problem in fundamental groups of finite graphs of groups with free abelian vertex groups can be solved in polynomial time on a strongly generic set. Furthermore, the conjugacy problem in groups with more than one end can be solved with a strongly generic algorithm which has essentially the same time complexity as the word problem. These are rather striking results as the word problem might be easy, but the conjugacy problem might be even undecidable. Finally, our results yield another proof that the set where the conjugacy problem of the Baumslag group G(1,2) is decidable in polynomial time is also strongly generic.

关键词： generic case complexity amenability Schreier graph HNN extension amalgamated product conjugacy problem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：