This thesis examines the question of how it is possible to improve search techniques by better understanding hidden structure in Boolean Satisfiability problems. The backdoor structure, once found, makes a Satisfiability problem easy. This work provides ways of finding backdoors for analysis. It also provides a general theoretical description of what back doors represents.

No description available.

A wide range of problems can be formalized as a set of constraints that need to be satisfied. In fact, such a model is called a constraint satisfaction problem (CSP). Another way to represent a problem is to express it as a formula in propositional logic, or, in other words, a Boolean satisfiability problem (SAT). In the quest to find efficient algorithms for solving instances of CSP and SAT specialised software has been developed. It is, however, not clear when should we choose a SAT-solver over a constraint solver (and vice versa). CSP-solvers are known for their domain-specific reasoning, whereas SAT-solvers are considered to be remarkably fast on Boolean instances. In this thesis we tackle these issues by investigating the connections between CSP and SAT. In order to answer the question why SAT-solvers are so efficient on certain classes of CSP instances, we first present the various ways one can encode a CSP instance into SAT. Next, we show that with some encodings SAT-solvers simulate the effects of enforcing a form of local consistency, called k-consistency, in expected polynomial-time. Thus SAT-solvers are able to solve CSP instances of bounded-width structure efficiently in contrast to conventional constraint solvers. By considering the various ways one can encode CSP domains into SAT, we give theoretical reasons for choosing a particular SAT encoding for several important classes of CSP instances. In particular, we show that with this encoding many problem instances that can be solved in polynomial-time will still be easily solvable once they are translated into SAT. Furthermore, we show that this is not true for several other encodings. Finally, we compare the various ways one can use a SAT-solver to solve the classical problem of the pigeonhole principle. We perform both theoretical and empirical comparison of the various encodings. We conclude that none of the known encodings for the classical representation of the problem will result in an efficiently-solvable SAT instance. Thus in this case constraint solvers are a much better choice.

- / -

We investigate definability in henselian fields. Specifically, we are interested in those sets and substructures that are existentially definable or definable with `few' parameters. Our general approach is to use various versions of henselianity to understand the `local structure' of these definable sets. The fields in which we are most interested are those of positive characteristic, for example the local fields F_q((t)), but many of our methods and results also apply to p-adic and real closed fields. In positive characteristic we have to deal with inseparable field extensions and we develop the method of Λ-closure to `translate' inseparable field extensions into separable ones. In the first part of the thesis we focus on existentially definable sets, which are projections of algebraic sets. Our main tool is the Implicit Function Theorem (for polynomials) which is equivalent to t-henselianity, by work of Prestel and Ziegler. This enables us to prove that existentially definable sets are `large' in various senses. Using the Implicit Function Theorem, we also obtain a nonuniform local elimination of the existential quantifier. The non-uniformity and local character of this result at present forms an obstacle to full quantifier-elimination. From these technical statements we can deduce characterisations of, for example, existentially definable subfields and existentially definable transcendentals. We prove that a dense, regular extension of t-henselian fields is existentially closed which, in particular, implies the old result of Ershov that F_p(t)^h ≤_Ǝ F_p((t)). Using the existential closedness of large fields in henselian fields, we are able to apply many of these results to large fields. This answers questions for imperfect large fields that were answered in the perfect case by Fehm.</p> In the second part of the thesis, we work with power series fields F((t)) and subsets which are F- definable (and not contained in F). We use a `hensel-like' lemma to characterise F-orbits of (singleton) elements of F((t)). It turns out that all such orbits are Ǝ-t-definable. Consequently, we may apply our earlier results about existentially definable subsets to F-definable subsets. We can use this to characterise F-definable subfields of F((t)). As a further corollary, we obtain an Ǝ-0̸-definition of F_p[[t]] in F<sub>p<sub>((t)).

Στη διατριβή αυτή θα ασχοληθούμε με την Μπουλιανή ανάλυση σαν μια κατ'ευθείαν γενίκευση της μη συμβατικής ανάλυσης του Robinson, δηλ. της θεωρίας των Υπεργινομένων και τις εφαρμογές της στη θεωρία των Ασαφών συνόλων. / --