University of California, Berkeley
Fall 2000
Advisor: Christos Papadimitriou
Download entire document (108 pages, postscript)
Abstract:
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
(Sigma2), and have eluded attempts to apply a similar
methodology for Sigma2. In this dissertation, we address intractability, approximability,
and limits of approximability for these problems.
We prove that several of these problems are Sigma2-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
Sigma2 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\eps, and for several, we obtain n1-\eps, 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.
[Home][Research][Teaching][Theory links][Other]