Simplicity and Strong Reductions
Simplicity and Strong Reductions
复制标题
简单性和强大的减少
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Stephen A. Fenner
中科院分区：
文献类型：
--
作者：
M. Schaefer;Stephen A. Fenner
如果一个集合不包含任何无穷NP子集，则称它为NP免疫的;如果它位于NP中，则称它为NP简单的，并且它的补集是NP免疫的。Hartmanis，Li和Yehsa在1986年证明了NP的m-硬（多-一硬）集是NP免疫的，除非NP包含在SUBEXP中。另一方面，我们可以展示一个相对化的世界，其中存在一个\NP-简单集，它在图灵约化下是完备的，甚至在合取约化下也是完备的。因此，我们可以问，原来的结果在多大程度上推广到强度介于多1约化和图灵约化之间的约化。我们证明了NP的正有界真值表完备集是NP-简单的，除非UP包含在SUBEXP中。在更强的假设下，UP和co UP的交集不包含在SUBEXP中，甚至没有NP的有界真值表完备集是NP-简单的。进一步的结果为不同的减少，包括一个类似的定理NEXP不需要任何假设。我们使用不可分集得到结果。这种技术在真值表甚至（诚实的）图灵约简的研究中非常强大。
A set is called NP-immune if it does not contain any infinite NP subsets, and NP-simple if it lies in NP, and its complement is NP-immune. Hartmanis, Li and Yehsa proved in 1986 that no m-hard (many-one hard) set for NP is NP-immune unless NP is contained in SUBEXP. On the other hand we can exhibit a relativized world in which there is an \NP-simple set that is complete under Turing reductions, even conjunctive reductions. We can therefore ask to what extent the original result generalizes to reductions which lie in strength in between many-one and Turing reductions. We show that no positive bounded truth-table complete set for NP is NP-simple, unless UP is contained in SUBEXP. Under the stronger assumption that the intersection of UP and co UP is not contained in SUBEXP it is even true that no bounded truth-table complete set for NP is NP-simple. Further results for different reductions are shown including a similar theorem about NEXP which does not require any assumptions. We derive the results by the use of inseparable sets. This technique turns out to be very powerful in the study of truth-table and even (honest) Turing reductions.