On simple and creative sets in NP
Steven Thomas Homer · Theoretical Computer Science · 1986
Two structurally defined types of NP-sets are studied. k -Simple sets are defined and shown to exist in NP. Other properties of these sets are investigated. k -Creative sets, as previously defined by Joseph and Young (1985), are next considered. A new condition is given which implies that a set is k -creative. Several previously considered NP-complete sets are proved to be k -creative.