一句话：回答了粗可计算性中的 Gamma 公开问题，澄清 oracle 集合的 Gamma 值能否严格介于 0 与 1/2 之间。
本文研究粗可计算性（coarse computability）框架下的 Gamma 问题。该问题由 Andrews、Cai、Diamondstone、Jockusch 和 Lempp 提出，询问 oracle 集合的 Gamma 值能否严格位于 0 与 1/2 之间。Gamma 值度量的是：相对于该 oracle 可计算的每个集合，在密度意义上被可计算集合逼近的程度；该值越接近 1，oracle 越接近可计算。论文对该开放问题给出解答，从而澄清 Gamma 值可能取值范围中 0 与 1/2 之间的情形。摘要未明示具体答案或构造，但核心贡献是解决这一来自复杂度理论、与渐近密度、可计算可追踪性和 1-随机性相关的公开问题。
We answer in this paper an open question (known as the "Gamma question"), related to the recent notion of coarse computability, which stems from complexity theory. The question was formulated by Andrews, Cai, Diamondstone, Jockusch and Lempp in "Asymptotic density, computable traceability and 1-randomness" [1]. The Gamma value of an oracle set measures to what extent each set computable with the oracle is approximable in the sense of density by a computable set. The closer to 1 this value is, the closer the oracle is to being computable. The Gamma question asks whether this value can be strictly in between 0 and 1/2.
DOI 原文 ·
@inproceedings{paperbot4359,
title = {An answer to the Gamma question},
author = {Benoit Monin},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209117}
}