Structural properties of nondeterministic complete sets
Steven Thomas Homer · 2002
Two aspects of the structure of complete sets for NE and larger nondeterministic time classes are surveyed. First, differences between complete sets arising from various polynomial-time reductions are proved. Immunity properties of these complete sets are then considered. It is shown that NE-complete sets (and their complements) have dense E subsets and dense UP subsets. All of these results hold for nondeterministic time classes containing NE. Some consequences for NP are noted.>