On simple and creative sets in NP

AbstractTwo 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