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

generic complexity of Finitely Presented Monoids and Semigroups

COMPUTATIONAL complexity 2011年第1期20卷 21-50页

作者： Kambites, Mark Univ Manchester Sch Math Manchester M13 9PL Lancs England

We study the generic properties of finitely presented monoids and semigroups, and the generic-case complexity of decision problems for them. We show that for a finite alphabet A of size at least 2 and positive integers k and m, the generic A-generated k-relation monoid and semigroup (defined using any of several stratifications) satisfies the small overlap condition C(m). It follows that the generic finitely presented monoid has a number of interesting semigroup-theoretic properties and, by a recent result of the author, admits a linear time solution to its word problem and a regular language of unique normal forms for its elements. Moreover, the uniform word problem for finitely presented monoids is generically solvable in polynomial time.

关键词： generic-case complexity monoids semigroups finite presentations

来源：评论

学校读者我要写书评

暂无评论

Average-case complexity and decision problems in group theory

引用

ADVANCES IN MATHEMATICS 2005年第2期190卷 343-359页

作者： Kapovich, I Myasnikov, A Schupp, P Shpilrain, V Univ Illinois Dept Math Urbana IL 61801 USA CUNY City Coll Dept Math New York NY 10031 USA

We investigate the average-case complexity of decision problems for finitely generated groups, in particular, the word and membership problems. Using our recent results on "generic-case complexity", we show that if a finitely generated group G has word problem solvable in subexponential time and has a subgroup of finite index which possesses a non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem of G is linear time, uniformly with respect to the collection of all length-invariant measures on G. This results applies to many of the groups usually studied in geometric group theory: for example, all braid groups B-n all groups of hyperbolic knots, many Coxeter groups and all Artin groups of extra-large type. (C) 2003 Elsevier Inc. All rights reserved.

关键词： average-case complexity generic-case complexity decision problems finitely presented groups

来源：评论

学校读者我要写书评

暂无评论

On the generic complexity of the searching graph isomorphism problem

引用

GROUPS complexity CRYPTOLOGY 2015年第2期7卷 191-193页

作者： Rybalov, Alexander Omsk State Tech Univ Prospekt Mira 11 Omsk 644050 Russia

A generic-case approach to algorithmic problems was suggested by Myasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies the behavior of an algorithm on typical inputs and ignores the rest of the inputs. In this paper we consider generic complexity of the searching graph isomorphism problem. We fit this problem in the frameworks of generic complexity and prove that its natural subproblem is generically hard provided that the searching graph isomorphism problem is hard in the worst case.

关键词： generic-case complexity graph isomorphism searching graph isomorphism problem

来源：评论

学校读者我要写书评

暂无评论

generic case completeness

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第8期82卷 1268-1282页

作者： Miasnikov, Alexei Ushakov, Alexander Stevens Inst Technol Dept Math Hoboken NJ 07030 USA

In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete. (C) 2016 Elsevier... 详细信息

关键词： generic-case complexity Completeness Randomized problems Bounded halting problem

来源：评论

学校读者我要写书评

暂无评论

generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups

引用

PACIFIC JOURNAL OF MATHEMATICS 2006年第1期223卷 113-140页

作者： Kapovich, I Schupp, P Shpilrain, V Univ Illinois Dept Math Urbana IL 61801 USA CUNY City Coll Dept Math New York NY 10031 USA

We prove that Whitehead's algorithm for solving the automorphism problem in a fixed free group F-k has strongly linear time generic-case complexity. This is done by showing that the "hard" part of the algorithm terminates in linear time on an exponentially generic set of input pairs. We then apply these results to one-relator groups. We obtain a Mostow-type isomorphism rigidity result for random one-relator groups: If two such groups are isomorphic then their Cayley graphs on the given generating sets are isometric. Although no nontrivial examples were previously known, we prove that one-relator groups are generically complete groups, that is, they have trivial center and trivial outer automorphism group. We also prove that the stabilizers of generic elements of F-k in Aut(F-k) are cyclic groups generated by inner automorphisms and that Aut(F-k)-orbits are uniformly small in the sense of their growth entropy. We further prove that the number I-k(n) of isomorphism types of k-generator one-relator groups with defining relators of length n satisfies c(1)/n (2k - 1)(n) <= I-k(n) <= c(2)/n(2k- 1)(n), where c(1), c(2) are positive constants depending on k but not on n. Thus I-k(n) grows in essentially the same manner as the number of cyclic words of length n.

关键词： one-relator groups Whitehead algorithm generic-case complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：