Separating NE from Some Nonuniform Nondeterministic Complexity Classes

摘要

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 (is contained in) R_(n~(o(1))-T)~(NP)(TALLY); (2)NE (is contained in) R_m~(SN)(SPARSE); and (3) NE (is contained in) P_(n~k-T)~(NP)~k for all k ≥ 1. 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'contains A and A' - A is not of sub-exponential density.