Title: A study of the structure of np (polynomial density)
Abstract: 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.
Publication Year: 1983
Publication Date: 1983-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot