A constraint satisfaction problem (CSP) can be represented as two structures: the structure induced by the variables and the structure induced by the constraint language. Both these parameters are amenable to restrictions which affects the complexity of the resulting problems. In this thesis we shall use both constraint language restrictions and structural restrictions in order to create problems that can be solved as efficiently as possible. The language restrictions are based on creating a language that in terms of frozen partial clone theory has the largest number of polymorphic functions. Such a language can according to the Galois connection between functions and relations be implemented by as many languages as possible and is therefore the Boolean language with the lowest complexity. The structural restrictions are mainly based on limiting the number of times a variable is allowed to occur in an instance. We shall prove that the easiest language does not contain a Delta-matroid relation and is NP-complete even with the very restricted structure where no variable can occur in more than two constraints. We also give a branch-and-reduce algorithm for this problem with time complexity O(1.0493^n). This problem is then related to the exponential-time hypothesis, which postulates that k-SAT is not sub-exponential for k >= 3. We show that the exponential-time hypothesis holds if and only if this restricted problem is not sub-exponential, if and only if all NP-complete Boolean languages are not sub-exponential. In the process we also prove a stronger version of Impagliazzo's sparsification lemma for k-SAT; namely that all finite, NP-complete Boolean languages can be sparsified into each other. This should be contrasted with Santhanam's negative result which states that the same does not hold for all infinite Boolean languages.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

No description available.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

<p>In this thesis local methods are made available as a tool to study the<br />unary parts of clones (or, equivalently, the weak Krasner algebras). Using the<br />language of model theory and Galois connections we develop a link between<br />homomorphism-homogeneous relational structures and local methods, via the<br />notion of endolocality. The theoretical results that are obtained are used to develop<br />a systematic theory for the classification of homomorphism-homogeneous<br />relational structures.</p> / <p>U ovoj tezi su razvijene lokalne metode koje se mogu koristiti za izu-<br />ˇcavanje unarnih delova klonova (ili, ekvivalentno, slabih Krasnerovih algebri).<br />Koriˇs&acute;cenjem jezika teorije modela i Galoovih veza uspostavljen je odnos izmedu<br />homomorfizam-homogenih relacionih struktura i lokalnih metoda, preko pojma<br />endolokalnosti. Dobijeni teoretski rezultati su upotrebljeni za razvoj sistematske<br />teorije za klasifikaciju homomorfizam-homogenih struktura.</p>