Banishing Robust Turing Completeness
Banishing Robust Turing Completeness
复制标题
消除鲁棒图灵完备性
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
N. Vereshchagin
中科院分区：
文献类型：
--
作者：
L. Hemaspaandra;Sanjay Jain;N. Vereshchagin
本文证明了“承诺类”是如此脆弱的结构，他们不鲁棒（即相对于所有的预言机）拥有图灵哈特集，即使在类远远大于自己。特别是，本文表明，FewP不具有鲁棒图灵硬集UP和IP ZPP不具有鲁棒图灵硬集ZPP。因此，ZPP、R、coR、UP、UP、FewP、FewP和IP不鲁棒地拥有图灵完备集。这两者都解决了在图灵约简下缺乏鲁棒向下闭包的promise类（例如，R，UP，FewP）可能鲁棒地具有图灵完备集，并且扩展了已知不鲁棒地包含多-一完备集的类的范围。
This paper proves that “promise classes” are so fragilely structured that they do not robustly (i.e. with respect to all oracles) possess Turinghard sets even in classes far larger than themselves. In particular, this paper shows that FewP does not robustly possess Turing hard sets for UP∩coUP and IP∩coIP does not robustly possess Turing hard sets for ZPP. It follows that ZPP, R, coR, UP∩coUP, UP, FewP∩coFewP, FewP, and IP∩coIP do not robustly possess Turing complete sets. This both resolves open questions of whether promise classes lacking robust downward closure under Turing reductions (e.g., R, UP, FewP) might robustly have Turing complete sets, and extends the range of classes known not to robustly contain many-one complete sets.