已入深夜,您辛苦了!由于当前在线用户较少,发布求助请尽量完整的填写文献信息,科研通机器人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
更新
大幅提高文件上传限制,最高150M (2024-4-1)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
1秒前
okk完成签到 ,获得积分10
3秒前
紫苑发布了新的文献求助20
6秒前
Maples发布了新的文献求助10
7秒前
7秒前
小马甲应助qianyuan采纳,获得10
7秒前
小李发布了新的文献求助10
11秒前
自由的蜡烛完成签到,获得积分10
13秒前
潘潘完成签到,获得积分10
14秒前
16秒前
19秒前
22秒前
赘婿应助科研通管家采纳,获得10
23秒前
酷波er应助科研通管家采纳,获得10
23秒前
qianyuan发布了新的文献求助10
24秒前
无花果应助小李采纳,获得10
24秒前
唠叨的弘文完成签到,获得积分10
26秒前
佟语雪完成签到,获得积分10
26秒前
30秒前
禾苗完成签到,获得积分10
30秒前
JamesPei应助hzauhzau采纳,获得10
32秒前
田様应助qianyuan采纳,获得10
35秒前
35秒前
44秒前
顾矜应助微之徒采纳,获得10
44秒前
fang完成签到 ,获得积分10
45秒前
极度厌蠢应助ltb采纳,获得30
47秒前
hzauhzau发布了新的文献求助10
50秒前
jiejie发布了新的文献求助10
52秒前
自然的南露完成签到 ,获得积分10
54秒前
动听的一一完成签到 ,获得积分10
56秒前
潇潇雨歇应助yueyue采纳,获得10
59秒前
1分钟前
超困zzZ完成签到,获得积分10
1分钟前
1分钟前
1分钟前
彭于晏应助孤独的根号3采纳,获得10
1分钟前
yang完成签到,获得积分10
1分钟前
1分钟前
英姑应助Focus_BG采纳,获得10
1分钟前
高分求助中
Comprehensive natural products III : chemistry and biology 3000
进口的时尚——14世纪东方丝绸与意大利艺术 Imported Fashion:Oriental Silks and Italian Arts in the 14th Century 800
Glucuronolactone Market Outlook Report: Industry Size, Competition, Trends and Growth Opportunities by Region, YoY Forecasts from 2024 to 2031 800
Zeitschrift für Orient-Archäologie 500
The Collected Works of Jeremy Bentham: Rights, Representation, and Reform: Nonsense upon Stilts and Other Writings on the French Revolution 320
Equality: What It Means and Why It Matters 300
A new Species and a key to Indian species of Heirodula Burmeister (Mantodea: Mantidae) 300
热门求助领域 (近24小时)
化学 医学 生物 材料科学 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 基因 遗传学 物理化学 催化作用 细胞生物学 免疫学 冶金
热门帖子
关注 科研通微信公众号,转发送积分 3346644
求助须知:如何正确求助?哪些是违规求助? 2973290
关于积分的说明 8658745
捐赠科研通 2653712
什么是DOI,文献DOI怎么找? 1453317
科研通“疑难数据库(出版商)”最低求助积分说明 672815
邀请新用户注册赠送积分活动 662753