Structural properties of disjoint NP-pairs and the random oracle model.

摘要

There are three parts to this dissertation. The first two parts are motivated by the reexamination of a conjecture put forth by Even, Selman and Yacobi [1984], denoted the ESY conjecture, regarding the hardness of problems separating pairs of disjoint sets in NP. The conjecture poses that every disjoint pair of NP problems contains a separator that is not NP-hard. This original statement of the conjecture concerns Turing hardness. In order to attempt progress towards the conjecture, we consider variants of the conjecture under different types of reductions. We observe how the implications of the conjecture vary as the notion of hardness is strengthened from Turing hardness to many-one hardness. In particular, our focus centers on a middle ground, considering truth-table and bounded truth-table reductions.;Before approaching the conjecture, we first study the structure of the class of non-empty disjoint pairs of sets in NP, denoted DisjNP. There is a natural relation between the non-existence of a complete pair in DisjNP for a reduction type r and the ESY conjecture holding under the notion of r hardness. We show that the existence of a complete pair for DisjNP under bounded truth-table reductions is equivalent to the existence of a many-one complete pair for DisjNP. The second part builds on this, considering the relation between the ESY conjecture variants for bounded truth-table and many-one reductions. We show that the ESY conjecture variants for length-increasing bounded truth-table reductions and many-one reductions are equivalent, as both statements are equivalent to NP ≠ CoNP. Also, we attempt to remove the length-increasing requirement on the bounded truth-table reduction, however cannot do so without additional assumptions. Further, we observe that the ESY conjecture versions for truth-table and Turing reductions share many of the same strong consequences with each other, namely NP ≠ CoNP, NP ≠ UP, and sat ∉ NPSV, where sat is the multivalued function mapping Boolean formulas to their satisfying assignments. This provides evidence that these two versions are more powerful statements than their bounded truth-table and many-one reduction counterparts.;The third part concerns the structure of complexity classes under the random oracle model. There are numerous results regarding the structure of complexity classes under the random oracle model, beginning with a separation of NP and CoNP relative to a random oracle [Bennett and Gill, 1981], and more recently obtaining the polynomial hierarchy is strict relative to a random oracle [Rossman et al., 2015]. There is a rich structure of separations under the random oracle model. Due to the nature of Kolmogorov's zero one law, these separation results are definitive, unlike cases in the standard oracle model where relations go different ways under different oracles. We show that relative to a random oracle R, UPR ≠ co-UPR. Additionally, we provide evidence toward tight space-bounds for 1-tape deterministic time t(n). We show that relative to every oracle A, DTIME1 A(t(n), √t(n)), the class of languages accepted by 1-tape deterministic time t(n) Turing machines with at most √t(n) oracle queries, is contained in DSPACEA(√t(n))). In contrast, we show that relative to a random oracle R, DTIME1 R(O(t(n)), √t(n) + 1) (n/a) DSPACER(o(√t(n))). In other words, there is no better space efficient simulation of 1-tape deterministic time t(n) Turing machines than √t(n) deterministic space. Lastly, we show that relative to a random oracle R, DSPACER(O(n)) (n/a) DTIMER(2 (1-epsilon)n), demonstrating that a PSPACE analog of the "Exponential Time Hypothesis" for NP is true relative to a random oracle.