Existential theorems in computational complexity theory: Size and robustness.

摘要

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.; Chapter 2 is dedicated to abstract complexity theory. 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. On the other hand, only classes of functions that are small can have the compression property.; Chapter 3 is dedicated to structural complexity. We show that, with probability one on the set of oracles, there is a set in NP{dollar}sp{lcub}A{rcub}{dollar} that asymptotically splits in half any infinite set in P{dollar}sp{lcub}A{rcub}{dollar}. 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.; Chapter 4 is dedicated to concrete complexity. 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.; The appendix is an excursion into the realm of experimental algorithms. We show that a heuristic based on the simulated annealing paradigm is superior, in terms of fairness, to all the methods that have been proposed in U.S. history for apportioning seats in the House of Representatives. In order to allow this assertion of superiority to be rigorous, we drive the heuristic search with an exact dynamic programming evaluation of the #P-complete fairness-quality of those states visited.