We investigate the question whether NE can be separated from the reduction closures of tally sets, sparse sets and NP. We show that (1) NE Ë eq RNPno(1)-T(TALLY)mathrm{NE}notsubseteq R^{mathrm{NP}}_{n^{o(1)}-T}(mathrm{TALLY}); (2) NE Ë eq RSNm(SPARSE)mathrm{NE}notsubseteq R^{SN}_{m}(mathrm{SPARSE}); (3) NEXP Ë eq PNPnk-Tkmathrm{NEXP}notsubseteq mathrm{P}^{mathrm{NP}}_{n^{k}-T}^{k} for all k≥1; and (4) NE Ë eq Pbtt(NPÅSPARSE)mathrm{NE}notsubseteq mathrm{P}_{btt}(mathrm{NP}oplusmathrm{SPARSE}). Result (3) extends a previous result by Mocas to nonuniform reductions. We also investigate how different an NE-hard set is from an NP-set. We show that for any NP subset A of a many-one-hard set H for NE, there exists another NP subset A′ of H such that A′⊇ A and A′−A is not of sub-exponential density.
展开▼
机译：我们研究是否可以将NE与计数集，稀疏集和NP的约简闭包分开。我们证明（1）NEËeq R NP n o（1） -T （TALLY）mathrm {NE} notsubseteq R ^ { mathrm {NP}} _ {n ^ {o（1）}-T}（mathrm {TALLY}）; （2）NEËeqR SN m （SPARSE）mathrm {NE} notsubseteq R ^ {SN} _ {m}（mathrm {SPARSE}）; （3）NEXPËeq P NP n k -T / n k mathrm {NEXP} notsubseteq mathrm {对于所有k≥1的P} ^ {mathrm {NP}} _ {n ^ {k} -T} / n ^ {k}； （4）NE eq P btt （NPÅSPARSE）mathrm {NE} notsubseteq mathrm {P} _ {btt}（mathrm {NP} oplusmathrm {SPARSE}）。结果（3）将Mocas的先前结果扩展为非均匀归约。我们还研究了NE硬集与NP集有何不同。我们表明，对于NE的多一硬集H的任何NP子集A，都存在H的另一个NP子集A'，使得A'⊇A和A'-A的子指数密度不大。
展开▼
