Immunity of Complete Problems

Two necessary and sufficient conditions for all E-complete sets to contain dense P subsets are shown. We then prove that every ≤ p m -hard for E set and its complement contain dense E∩UP subsets. As a corollary, every NE-complete set and its complement contain dense E∩UP subsets.

Authors

• S. Homer
• J. Wang

Keywords

No keywords are indexed for this paper.