Complexity profiles and generic Muchnik reducibility
Complexity profiles and generic Muchnik reducibility
复制标题
复杂性概况和通用的 Muchnik 可归约性
DOI：
10.1016/j.aim.2023.109397
复制
发表时间：
2024
影响因子：
1.7
通讯作者：
Soskova, Mariya
中科院分区：
文献类型：
--
作者：
Andrews, Uri;Miller, Joseph S.;Schweber, Noah;Soskova, Mariya
我们利用一般的Muchnik约化研究了Cantor和Baire空间展开的相对计算复杂性。我们证明了通过可数次一元关系或闭关系展开康托空间不能给出严格介于康托空间的次数和Baire空间的次数之间的一般Muchnik次数。类似地，在Δ2 1-wadge确定性的假设下，我们证明了通过可数多个一元或闭关系展开的Baire空间不能给出严格介于Baire空间的次数和Borel完备度之间的一般Muchnik度.另一方面，我们给出了一种严格介于Cantor空间的度与Baire空间的度之间以及Baire空间的度与Borel完备度之间的度的构造。
We study the relative computational complexity of expansions of Cantor and Baire space in terms of generic Muchnik reducibility. We show that no expansion of Cantor space by countably many unary or closed relations can give a generic Muchnik degree strictly between the degree of Cantor space and the degree of Baire space. Similarly, assuming Δ 2 1-Wadge determinacy we show that no expansion of Baire space by countably many unary or closed relations can give a generic Muchnik degree strictly between the degree of Baire space and the Borel complete degree. On the other hand, we provide a construction of a degree strictly between the degree of Cantor space and the degree of Baire space and also between the degree of Baire space and the Borel complete degree.
登录
查看更多内容
可数结构的通用副本
影响因子：
0.8
作者：
C. Ash;J. Knight;M. Manasse;T. Slaman
通讯作者：
T. Slaman
通用的 muchnik 可归约性和域的表示
影响因子：
1
作者：
R. Downey;Noam Greenberg;Joseph S. Miller
通讯作者：
Joseph S. Miller
比较两个版本的实数
DOI：
10.1017/jsl.2015.77
发表时间：
2016
期刊：
The Journal of Symbolic Logic
影响因子：
--
作者：
Gregory Igusa;J. Knight
通讯作者：
J. Knight
贝尔空间的可约性和确定性
DOI：
--
发表时间：
1982
期刊：
影响因子：
--
作者：
W. Wadge
通讯作者：
W. Wadge
有效模型理论与递归模型理论
DOI：
--
发表时间：
1990
期刊：
Journal of Symbolic Logic (JSL)
影响因子：
--
作者：
John Chisholm
通讯作者：
John Chisholm