Browse Theses

The theoretical computer science methodology for dealing with NP optimization problems has been highly successful in exposing intractability through the theory of NP-completeness, developing approximation algorithms, and establishing limits on approximability. A number of natural and practically important problems relating to logic minimization lie beyond NP in the second level of the Polynomial Hierarchy ( S ^P ₂ ), and have eluded attempts to apply a similar methodology for S ^P ₂ . In this dissertation, we address intractability, approximability, and limits of approximability for these problems.

We prove that several of these problems are S ^P ₂ -complete, including the Minimum Equivalent DNF problem, solving a well-known problem that had been open for 24 years. We present a dozen natural optimization problems that are a mix of practically important problems and more basic combinatorial problems and show that they are complete for appropriate levels of the Polynomial Hierarchy. A variant of one of these problems turns out to require only limited nondeterminism; to capture the complexity of this problem we define a new complexity class between coNP and S ^P ₂ and show that the problem is complete for the new class.

We develop a technique for showing that these problems are hard to approximate to within very large factors. In contrast to the situation for NP optimization problems, our technique does not rely on Probabilistically Checkable Proofs in any way; instead we employ a new type of code, which we call an or-code , to give simple and powerful gap-producing reductions. We show close connections between or-codes and dispersers , and we give randomized and explicit constructions of or-codes based on dispersers, as well as efficient encoding and list-decoding procedures. For all of the problems we consider, we obtain inapproximability ratios of n ý , and for several, we obtain n 1ýý , which is optimal up to lower order terms.

We give approximation algorithms for minimization problems in the Polynomial Hierarchy. Previously, no approximation algorithms with formal approximation guarantees were known for any of the problems we consider, despite the practical importance of several of them. Our algorithms are based on an elegant technique in learning theory, and they fit into a generic framework that can be applied to a wide array of minimization problems in the Polynomial Hierarchy. Our algorithms are actually approximation schemes : they exhibit a tradeoff between approximation quality and asymptotic running time. For most of the problems we consider, we achieve approximation ratios of n /log n with an expected polynomial running time.