Nondeterminism and optimization

Abstract

The study of the power of nondeterminism is central to complexity theory. However, it remains unclear how nondeterminism can be used to characterize computational optimization problems. In this dissertation, a "Guess-then- Check" model GC is introduced to systematically study nondeterminism. Techniques are developed to construct GCcomplete languages and to improve recent results in the study of nondeterministic computation. GC computations with weak checkers are studied in detail based on precise circuit characterizations of logaxithraic-time alternating Turing machines. The complexity, fixed-parameter tractability, and approximability of NP optiraization problems are extensively investigated based on GC computations with weak checkers. It is shown that the complexity of solution size-bounded optimization problems is precisely described by their usage of nondeteranism. It is also proved that:hxed-paxameter tractability and intractability of parameterized problems axe exactly characterized by different amounts of nondeterminism. A close relationship between the fixed-parameter tractability and the approximability of NP optimization problems is well established to study the nondeterminism characterization of approximability. Evidence is presented that our research gives a new insight into the computational properties of optimization problems.