Two results on complexities of decision problems of groups

计算机科学
作者
Uri Andrews,Matthew Harrison-Trainor,Meng-Che Ho
出处
期刊:Cornell University - arXiv
标识
DOI:10.48550/arxiv.2403.02492
摘要

We answer two questions on the complexities of decision problems of groups, each related to a classical result. First, C. Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the isomorphism problem for recursively presented groups. Second, the fact that every Turing degree appears as the degree of the word problem of a finitely presented group is shown independently by multiple people in the 1960s. We answer the analogous question for degrees of ceers instead of Turing degrees. We show that the set of ceers which are computably equivalent to a finitely presented group is $\Sigma^0_3$-complete, which is the maximal possible complexity.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
PDF的下载单位、IP信息已删除 (2025-6-4)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
大秀子完成签到,获得积分10
1秒前
艾哥完成签到,获得积分10
2秒前
情怀应助even采纳,获得10
2秒前
科研搬运工完成签到,获得积分0
3秒前
3秒前
4秒前
小火孩发布了新的文献求助10
4秒前
5秒前
5秒前
充电宝应助帝国超级硕士采纳,获得10
6秒前
在水一方应助cdddddy采纳,获得10
6秒前
鱼生完成签到,获得积分10
6秒前
7秒前
淡定的纹完成签到,获得积分10
8秒前
无奈凡波完成签到 ,获得积分10
8秒前
Kenny发布了新的文献求助10
8秒前
科研通AI2S应助科研通管家采纳,获得10
8秒前
共享精神应助科研通管家采纳,获得10
8秒前
我是老大应助科研通管家采纳,获得10
8秒前
搜集达人应助淡淡夕阳采纳,获得10
8秒前
8秒前
无花果应助科研通管家采纳,获得10
8秒前
orixero应助科研通管家采纳,获得10
8秒前
Akim应助科研通管家采纳,获得10
8秒前
Survivor应助科研通管家采纳,获得10
8秒前
leaf完成签到,获得积分10
8秒前
大模型应助科研通管家采纳,获得20
8秒前
打打应助科研通管家采纳,获得10
9秒前
Ava应助科研通管家采纳,获得30
9秒前
FashionBoy应助科研通管家采纳,获得10
9秒前
传奇3应助科研通管家采纳,获得10
9秒前
orixero应助科研通管家采纳,获得10
9秒前
顾矜应助科研通管家采纳,获得10
9秒前
小二郎应助科研通管家采纳,获得10
9秒前
orixero应助科研通管家采纳,获得10
9秒前
赘婿应助科研通管家采纳,获得10
9秒前
酷波er应助科研通管家采纳,获得10
9秒前
Hello应助科研通管家采纳,获得10
9秒前
9秒前
搜集达人应助科研通管家采纳,获得10
9秒前
高分求助中
The Mother of All Tableaux Order, Equivalence, and Geometry in the Large-scale Structure of Optimality Theory 2400
Ophthalmic Equipment Market by Devices(surgical: vitreorentinal,IOLs,OVDs,contact lens,RGP lens,backflush,diagnostic&monitoring:OCT,actorefractor,keratometer,tonometer,ophthalmoscpe,OVD), End User,Buying Criteria-Global Forecast to2029 2000
Cognitive Neuroscience: The Biology of the Mind 1000
Cognitive Neuroscience: The Biology of the Mind (Sixth Edition) 1000
Optimal Transport: A Comprehensive Introduction to Modeling, Analysis, Simulation, Applications 800
Official Methods of Analysis of AOAC INTERNATIONAL 600
ACSM’s Guidelines for Exercise Testing and Prescription, 12th edition 588
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 冶金 细胞生物学 免疫学
热门帖子
关注 科研通微信公众号,转发送积分 3958393
求助须知:如何正确求助?哪些是违规求助? 3504692
关于积分的说明 11119524
捐赠科研通 3235856
什么是DOI,文献DOI怎么找? 1788584
邀请新用户注册赠送积分活动 871232
科研通“疑难数据库(出版商)”最低求助积分说明 802605