The structural complexity of intractable search functions
Ashish V. Naik · 1995
The central theme in this dissertation is the complexity of computing witnesses for sets in NP. Since problems in NP are usually stated as problems, it is desirable that they have the property that computing a witness should not be harder than determining membership of the input. This property is known as reducing to decision. Disjunctive self-reducibility is the structural property that usually causes to be reducible to decision. We show under reasonable complexity assumptions about exponential time that there are languages that are not self-reducible for which reduces to decision. This result raises various related questions about the properties of self-1-helping, self-reducibility, the power of adaptiveness in reducing to decision, and the running time of reductions from to for SAT. Next, we consider the question: what is the smallest function class in which a satisfying assignment for a given input formula can be computed? We show that if there exists a single-valued nondeterministic polynomial-time transducer that computes satisfying assignments, then the polynomial hierarchy collapses to its second level. We also show for all k $\ge$ 0, that relative to a random oracle, some k-valued nondeterministic polynomial-time computable function cannot be computed by a $(k - 1)$-valued nondeterministic polynomial-time transducer. As a natural extension of search reduces to decision to randomized computation, we study a restricted form of interactive proof system that we call a natural proof system. We also study the power of adaptiveness in random-self-reductions and checking, and the relationship between random-self-reducible functions and self-correctable functions. Finally, motivated by their useful application in our study of functions, we study the internal structure of p-selective sets. We precisely characterize the relationship between p-selective sets and tally sets and study the question of existence of truth-table hard p-selective sets in NP.