A study of the structure of np (polynomial density)
Vivian Sewelson · 1983
In this thesis, we study the implications of having small sets, i.e. sets of polynomial density, in NP that are not in P. Intuitively this corresponds to having 'individual' Boolean formulas for which it is hard to determine satisfiability. The results obtained center around the theorem that there are sparse sets in NP-P if and only if E (NOT=) NE, i.e. we have a separation of complexity classes at the exponential level. We show that for any reasonable density, sets of that density exist in NP-P if and only if there is a noncollapse of certain deterministic and nondeterministic complexity classes. We explore the existence of sparse sets in the polynomial-time hierarchy. This investigation leads us to study the exponential-time hierarchy, a hierarchy defined similarly to the polynomial-time hierarchy, but one which behaves differently under relativization. It is this unexpected behavior that allows us to show, by relativization techniques, that it is possible for NP and CoNP to differ on the basic structural property of the existence of sparse sets.