The first part investigates CSPs for which satisfiability follows from the famous Lovász Local Lemma. Since its discovery in 1975 by Paul Erdős and László Lovász, it has been known that CSPs without dense spots of interdependent constraints always admit a satisfying assignment. However, an iterative procedure to discover such an assignment was not available. We refine earlier attempts at making the Local Lemma algorithmic and present a polynomial time algorithm which is able to make almost all known applications constructive.
In the second part, we leave behind the class of polynomial time tractable problems and instead investigate the randomized exponential time algorithm devised and analyzed by Uwe Schöning in 1999, which solves arbitrary clause satisfaction problems. Besides some new interesting perspectives on the algorithm, the main contribution of this part consists of a refinement of earlier approaches at derandomizing Schöning's algorithm. We present a deterministic variant which losslessly reaches the performance of the randomized original.
|Versandkostenfrei innerhalb Deutschlands|
Wollen auch Sie Ihre Dissertation veröffentlichen?