已入深夜,您辛苦了!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!祝你早点完成任务,早点休息,好梦!

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.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
wildeager发布了新的文献求助10
2秒前
慕青应助1820采纳,获得10
3秒前
xiaohe完成签到,获得积分10
4秒前
orixero应助YH采纳,获得10
6秒前
6秒前
kangk完成签到 ,获得积分10
7秒前
星辰大海应助简单的冬灵采纳,获得30
8秒前
虚幻初之发布了新的文献求助10
8秒前
9秒前
九号不会弹琴完成签到,获得积分20
10秒前
10秒前
11秒前
慢慢完成签到,获得积分10
13秒前
独特的初彤完成签到 ,获得积分10
13秒前
周千千完成签到 ,获得积分10
15秒前
斯文败类应助研友_LXOWx8采纳,获得10
15秒前
ndrise完成签到,获得积分10
15秒前
冷傲曼冬完成签到 ,获得积分10
15秒前
1820发布了新的文献求助10
16秒前
17秒前
自觉的云朵完成签到,获得积分10
18秒前
华仔应助youliang采纳,获得30
18秒前
ding应助科研通管家采纳,获得10
20秒前
脑洞疼应助科研通管家采纳,获得10
20秒前
小二郎应助科研通管家采纳,获得10
20秒前
华仔应助科研通管家采纳,获得10
20秒前
核桃应助科研通管家采纳,获得10
20秒前
小不点应助科研通管家采纳,获得10
20秒前
核桃应助科研通管家采纳,获得10
20秒前
20秒前
20秒前
无花果应助科研通管家采纳,获得10
20秒前
天天快乐应助科研通管家采纳,获得10
21秒前
21秒前
BowieHuang应助科研通管家采纳,获得10
21秒前
21秒前
21秒前
21秒前
干净的琦应助科研通管家采纳,获得10
21秒前
华仔应助科研通管家采纳,获得10
21秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
Handbook of pharmaceutical excipients, Ninth edition 5000
Aerospace Standards Index - 2026 ASIN2026 3000
Relation between chemical structure and local anesthetic action: tertiary alkylamine derivatives of diphenylhydantoin 1000
Signals, Systems, and Signal Processing 610
Discrete-Time Signals and Systems 610
Principles of town planning : translating concepts to applications 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 纳米技术 有机化学 物理 生物化学 化学工程 计算机科学 复合材料 内科学 催化作用 光电子学 物理化学 电极 冶金 遗传学 细胞生物学
热门帖子
关注 科研通微信公众号,转发送积分 6065515
求助须知:如何正确求助?哪些是违规求助? 7897800
关于积分的说明 16321645
捐赠科研通 5208002
什么是DOI,文献DOI怎么找? 2786195
邀请新用户注册赠送积分活动 1768889
关于科研通互助平台的介绍 1647755