Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 1996. Simultaneously published in the Technical Report series.
How strong are the results in computational complexity that assert, under certain hypotheses, the existence of an object? Are there many such objects, or are there few? To what extent can we relax the hypotheses and still maintain the same conclusions? These are the types of questions that are studied in this thesis. More precisely, we investigate some of the central existential results in computational complexity from the point of view of size and robustness. Below is a sample of the results in the thesis. We show that for any effective enumeration of computational devices that cover the whole set of computable functions and for any complexity measure satisfying a single axiom, neither the set of speedable functions nor the set of functions that generate complexity gaps is small from a topological point of view. We show that, with probability one on the set of oracles, there is a set in NP^A that asymptotically splits in half any infinite set in P^A. This is the strongest currently known relativized separation of NP from P. We also show that most (in the resource-bounded measure sense) sets that are computable in exponential time do not have even very weak membership-related properties that are computable in polynomial time. We prove that in almost all relativized worlds, there are very strong hard functions and pseudo random generators. This result is quite relevant in cryptography: it displays an efficient method that takes as input an exponentially long public random string and a polynomially long private random string and outputs an exponentially long public string that can be used as a private key because it looks truly random to any adversary circuit of exponential size. We show that all NP optimization problems admit a normal-form characterization involving the language of first-order logic and a unique system of weights. Various restrictions of the syntax generate classes containing important natural problems. Some such restrictions dictate good approximation properties for the corresponding classes in the case when positive weights are used. When negative weights are also allowed, the good approximation properties are not preserved.
