On the structure of intractable sets (binary relation)
John G. Geske · 1987
There are two parts to this dissertation. The first part is motivated by nothing less than a reexamination of what it means for a set to be NP-complete. Are there sets in NP that in a mathematically meaningful sense should be considered to be complete for NP, but that are not NP-complete in usual sense that every set in NP is $\leq\sbsp{m}{P}$-reducible to it? We define a noneffective binary relation that makes precise notion that the complexity of A is polynomially related to complexity of B, This relation yields new completeness and hardness notions for complexity classes, and we show that there are sets that are hard for NP that are not NP-hard in usual sense. We also show that there are sets that must be considered to be complete for E that are not even $\leq\sbsp{T}{P}$-complete for E. In a certain way, hardness and completeness with respect to relation we define is related to notion of almost everywhere (a.e.) complexity, and so we initiate this study by first investigating this notion. We state and prove a deterministic time hierarchy theorem for a.e. complexity that is as tight as Hartmanis-Stearns hierarchy theorem for infinitely often complexity. This result is a significant improvement over all previously known hierarchy theorems for a.e. complex sets. We derive similar, very tight, hierarchy theorems for sets that cannot be a.e. complex for syntactic reasons, but for which, intuitively, a.e. complex notions should exit. Similar results are applied to study of P-printable sets and sets of low generalized Kolmogorov complexity. The second part of this study deals with relativization. Does fact that DTIME(O (n)) $ ot=$ NTIME(n) help in leading us to a proof that P $ ot=$ NP? Does one imply other? We seek evidence that this is a hard. We construct an oracle that answers this question in affirmative, and we construct an oracle that answers this question in negative. We conclude that result that DTIME(O (n)) $ ot=$ NTIME(n) does not imply P $ ot=$ NP by recursive theoretic techniques. Finally, we study relationships between P, NP, and unambiguous and random time classes UP, and RP. Questions concerning these relationships are motivated by complexity issues to public-key cryptosystems. We prove that there exists a recursive oracle A such that P$\sp{A}$ $ ot=$ UP$\sp{A} ot=$ NP$\sp{A}$, and such that first inequality is strong, i.e., there exists a P$\sp{A}$-immune set in UP$\sp{A}$. Further, we constructed a recursive oracle B such that UP$\sp{B}$ contains an RP$\sp{B}$-immune set. As a corollary we obtain P$\sp{B}$ $ ot=$ RB$\sp{B} ot=$ NP$\sp{B}$ and both inequalities are strong. By use of techniques employed in proof that P$\sp{A} ot=$ UP$\sp{A} ot=$ NP$\sp{A}$, we are also able to solve an open problem raised by Book, Long and Selman.