Peter Jonsson
email: peter.jonsson@liu.se

Victor Lagerkvist

Gustav Nordh
email: gustav.nordh@liu.se

Bruno Zanuttini
email: bruno.zanuttini@unicaen.fr

Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis

The construction of exact exponential-time algorithms for NP-complete problems has for some time been a very active research area. Unfortunately, there is a lack of general methods for studying and comparing the time complexity of algorithms for such problems. We propose such a method based on clone theory and demonstrate it on the SAT problem. Schaefer has completely classified the complexity of SAT with respect to the set of allowed relations and proved that this parameterized problem exhibits a dichotomy: it is either in P or NP-complete. We show that there is a certain partial order on the NPcomplete SAT problems with a close connection to their worst-case time complexities; if a problem SAT(S) is below a problem SAT(S ′ ) in this partial order, then SAT(S ′ ) cannot be solved strictly faster than SAT(S). By using this order, we identify a relation R such that SAT(R) is the computationally easiest NP-complete SAT problem. This result may be interesting when investigating the borderline between P and NP since one appealing way of studying this borderline is to identify problems that, in some sense, are situated close to it (such as a 'very hard' problem in P or a 'very easy' NP-complete problem). We strengthen the result by showing that SAT(R)-2 (i.e. SAT(R) restricted to instances where no variable appears in more than two clauses) is NP-complete, too. This is in contrast to, for example, 1-in-3-SAT which is in P under the same restriction. We then relate SAT(R)-2 to the exponential-time hypothesis (ETH) and show that ETH holds if and only if SAT(R)-2 is not sub-exponential. This constitutes a strong connection between ETH and the SAT problem under both severe relational and severe structural restrictions, and it may thus serve as a tool for studying the borderline between sub-exponential and exponential problems. In the process, we also prove a stronger version of Impagliazzo et. al's sparsification lemma for k-SAT; namely that all finite, NP-complete Boolean languages can be sparsified into each other. This should be compared with Santhanam and Srinivasan's recent negative result which states that the same does not hold for all infinite Boolean languages.

Introduction

This paper is concerned with the SAT(S) class of problems: given a finite set of Boolean relations S, decide whether a conjunction of constraints (where only relations from S are used) is satisfiable or not. This class of problems is very rich and contains many problems that are highly relevant both theoretically and in practice. Since Schaefer's seminal dichotomy result [START_REF] Th | The complexity of satisfiability problems[END_REF], the computational complexity of SAT(S) is completely known: we know for which S that SAT(S) is polynomial-time solvable and for which it is NP-complete, and these are the only possible cases. On the other hand, judging from the running times of the many algorithms that have been proposed for different NP-complete SAT(S) problems, it seems that the computational complexity varies greatly for different S. As an example, 3-SAT (S consists of all clauses of length at most 3) is only known to be solvable in time O(1.3334 n ) [START_REF] Moser | A full derandomization of Schoening's k-SAT algorithm[END_REF] (where n is the number of variables), and so it seems to be a much harder problem than, for instance, positive 1-in-3-SAT (S consists only of the relation {(0, 0, 1), (0, 1, 0), (1, 0, 0)}), which can be solved in time O(1.0984 n ) [START_REF] Wahlström | Algorithms, Measures and Upper Bounds for Satisfiability and Related Problems[END_REF]. It is fair to say that we have a very vague understanding of the time complexity of NP-complete problems, and this fact is clearly expressed in [START_REF] Cygan | On problems as hard as CNFSAT[END_REF].

What the field of exponential-time algorithms sorely lacks is a complexity-theoretic framework for showing running time lower bounds.

In this paper, we initiate a systematic study of the relationships between the worst-case complexity of different SAT(S) problems, where we measure the complexity as a function of the number of variables. Ultimately, one would like to have a 'table' that for each NP-complete SAT(S) problem contains a number c such that SAT(S) can be solved in Θ(c n ) time. It seems that we are very far from this goal, unfortunately. Let us imagine a weaker qualitative approach: construct a table that for every two problems SAT(S) and SAT(S ′ ) tells us whether SAT(S) and SAT(S ′ ) can be solved equally fast, whether SAT(S) can be solved strictly faster than SAT(S ′ ), or vice versa. That is, we have access to the underlying total order on running times but we cannot say anything about the exact figures. Not surprisingly, we are far from this goal, too. However, this table can, in a sense, be approximated: there are non-trivial lattices that satisfy this property whenever S and S ′ are comparable to each other in the lattice. To obtain such lattices, we exploit clone theory [START_REF] Lau | Function Algebras on Finite Sets[END_REF][START_REF] Szendrei | Clones in Universal Algebra[END_REF]. This theory has proven to be very powerful when studying the complexity of SAT(S) and its multi-valued generalization known as constraint satisfaction problems (CSP) [START_REF] Bulatov | Classifying the complexity of constraints using finite algebras[END_REF]. However, it is not clear how this theory can be used for studying the worst-case running times for algorithms. We show how to use it for this purpose in Section 3, and our basic observation is that the lattice of partial clones [START_REF] Bodnarchuk | Galois theory for post algebras[END_REF][START_REF] Bodnarchuk | Galois theory for post algebras[END_REF] has the required properties. We would like to emphasize that this approach can be generalized in different ways; it is not restricted to Boolean problems and it is applicable to other computational problems such as counting and enumeration.

As a concrete application of this method, we identify the computationally easiest NP-complete SAT(S) problem in Section 4; by 'computationally easiest', we mean that if any NP-complete SAT(S) problem can be solved in O(c n ) time, then the easiest problem can be solved in O(c n ) time, too. This easiest NP-complete SAT(S) problem is surprisingly simple: S consists of a single 6-ary relation R = = = 1/3 which contains the three tuples (1, 0, 0, 0, 1, 1), (0, 1, 0, 1, 0, 1), and (0, 0, 1, 1, 1, 0). This result is obtained by making use of Schnoor and Schnoor's [START_REF] Schnoor | New algebraic tools for constraint satisfaction[END_REF] machinery for constructing weak bases. We note that there has been an interest in identifying extremely easy NP-complete problems before. For instance, van Rooij et. al have shown that the PARTITION INTO TRIANGLES problem restricted to graphs of maximum degree four can be solved in O(1.02445 n ) time [START_REF] Van Rooij | Partition into triangles on bounded degree graphs[END_REF]. They argue that practical algorithms may arise from this kind of studies, and the very same observation has been made by, for instance, Woeginger [START_REF] Woeginger | Exact algorithms for NP-hard problems: A survey[END_REF]. It is important to note that our results give much more information than just the mere fact that SAT(R = = = 1/3 ) is easy to solve; they also tell us how this problem is related to all other problems within the large and diverse class of finite SAT problems. This is one of the major advantages in using the clone-theoretical approach when studying these kind of questions. Another reason to study such problems is that they, in some sense, are 'close' to the borderline between problems in NP that are not complete and NP-complete problems (here we tacitly assume that P = NP). The structure of this borderline has been studied with many different aims and many different methods; two well-known examples are the articles by Ladner [START_REF] Ladner | On the structure of polynomial time reducibility[END_REF] and Schöning [START_REF] Schöning | A low and a high hierarchy within NP[END_REF].

We continue by studying the complexity of SAT(R = = = 1/3 ) and general SAT problems in greater detail by relating them to the EXPONENTIAL TIME HYPOTHESIS (ETH) [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF], i.e. the hypothesis that k-SAT cannot be solved in sub-exponential time for k ≥ 3. The ETH has recently gained popularity when studying the computational complexity of combinatorial problems, cf. the survey by Lokshtanov et al. [START_REF] Lokshtanov | Lower bounds based on the exponential time hypothesis[END_REF].

We first note (in Section 5) that SAT(R = = = 1/3 ) restricted to instances where no variable appears more than twice (the SAT(R = = = 1/3 )-2 problem) is still NP-complete (in contrast to, for instance, positive 1-in-3-SAT which is in P under the same restriction). We prove this by using results by Dalmau and Ford [START_REF] Dalmau | Generalized satisfiability with limited occurrences per variable: A study through delta-matroid parity[END_REF] combined with the fact that R = = = 1/3 is not a ∆-matroid relation. We then show (in Section 6) that the exponential-time hypothesis holds if and only if SAT(R = = = 1/3 )-2 cannot be solved in sub-exponential time, i.e. SAT(R = = = 1/3 )-2 is ETH-hard. By using this result, we show the following consequence: if ETH does not hold, then SAT(S)-k is sub-exponential for every k whenever S is finite. Impagliazzo et al. [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] have proved that many NP-complete problems in SNP (which contains the SAT problems) are ETH-hard. Thus, we strengthen this result when restricted to SAT problems. In the process, we also prove a stronger version of Impagliazzo et. al's [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] sparsification lemma for k-SAT; namely that all finite, NP-complete Boolean languages can be sparsified into each other. This can be contrasted with Santhanam's and Srinivasan's [START_REF] Santhanam | On the limits of sparsification[END_REF] recent negative result which states that the same does not hold for the unrestricted SAT problem and, consequently, not for all infinite Boolean languages.

The Boolean SAT problem

We begin by introducing the notation and basic results that will be used in the rest of this paper. The set of all n-tuples over {0, 1} is denoted by {0, 1} n . Any subset of {0, 1} n is called an n-ary relation on {0, 1}. The set of all finitary relations over {0, 1} is denoted by BR. A constraint language over {0, 1} is a finite set S ⊆ BR. Definition 1. The Boolean satisfiability problem over the constraint language S ⊆ BR, denoted SAT(S), is defined to be the decision problem with instance (V, C), where V is a set of Boolean variables, and C is a set of constraints {C 1 , . . . , C q }, in which each constraint C i is a pair (s i , R i ) with s i a list of variables of length m i , called the constraint scope, and R i an m i -ary relation over the set {0, 1}, belonging to S, called the constraint relation.

The question is whether there exists a solution to (V, C), that is, a function from V to {0, 1} such that, for each constraint in C, the image of the constraint scope is a member of the constraint relation. Using negation needs some extra care: let the sign pattern of a constraint γ(x 1 , . . . , x k ) be the tuple (s 1 , . . . , s k ), where s i = + if x i is unnegated, and s i = -if x i is negated. For each sign pattern we can then associate a relation that captures the satisfying assignments of the constraint. For example, the sign pattern of R NAE (x, ¬y, ¬z) is the tuple (+, -, -), and its associated relation is

R (+,-,-) NAE = {0, 1} 3 \ {(1, 0, 0), (0, 1, 1)}.
More generally, we use Γ k NAE to denote the corresponding language of not-all-equal relations (with all possible sign patterns) of length k. If φ is a SAT(Γ k NAE ) instance we use γ k NAE (x 1 , . . . , x k ) to denote a constraint in φ, where each x i is unnegated or negated. In the same manner we use Γ k SAT to denote the language consisting of all k-SAT relations of length k. When explicitly defining relations, we often use the standard matrix representation where the rows of the matrix are the tuples in the relation. For example,

R NAE =        0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0       
Note that the order of the rows in the matrix representation does not matter since this only correspond to a different order of the variables in a constraint.

Partial clones and the complexity of SAT

We will now show that the time complexity of SAT(S) is determined by the so-called partial polymorphisms of S. For a more in-depth background on SAT and algebraic techniques, we refer the reader to [START_REF] Böhler | Playing with boolean blocks, part I: Post's lattice with applications to complexity theory[END_REF] and [START_REF] Lau | Function Algebras on Finite Sets[END_REF], respectively. Note that most of the results in this section hold for arbitrary finite domains, but we present everything in the Boolean setting. We first note that any k-ary operation f on {0, 1} can be extended in a standard way to an operation on tuples over {0, 1}, as follows: for any collection of k tuples, t 1 , t 2 , . . . , t k ∈ R, the n-tuple f (t 1 , t 2 , . . . , t k ) is defined as follows:

f (t 1 , t 2 , . . . , t k ) = (f (t 1 [1], t 2 [1], . . . , t k [1]), f (t 1 [2], t 2 [2], . . . , t k [2]), . . . , f (t 1 [n], t 2 [n], . . . , t k [n])),
where t j [i] is the i-th component in tuple t j . We are now ready to define the concept of polymorphisms. Definition 3. Let S be a Boolean language and R an arbitrary relation from S. If f is an operation such that for all t 1 , t 2 , . . . , t k ∈ R it holds that f (t 1 , t 2 , . . . , t k ) ∈ R, then R is closed (or invariant) under f . If all relations in S are closed under f then S is closed under f . An operation f such that S is closed under f is called a polymorphism of S. The set of all polymorphisms of S is denoted by P ol(S). Given a set of operations F , the set of all relations that are closed under all the operations in F is denoted by Inv(F ).

Sets of operations of the form P ol(S) are referred to as clones. The lattice (under set inclusion) of all clones over the Boolean domain was completely determined by Post [START_REF] Post | The two-valued iterative systems of mathematical logic[END_REF] and it is usually referred to as Post's lattice. It is visualized in Figure 1 (see Appendix C). The following result forms the basis of the algebraic approach for analyzing the complexity of SAT, and, more generally, of constraint satisfaction problems. It states that the complexity of SAT(S) is determined, up to polynomial-time reductions, by the polymorphisms of S. Theorem 4. [START_REF] Jeavons | On the algebraic structure of combinatorial problems[END_REF] Let S 1 and S 2 be finite non-empty sets of Boolean relations. If P ol(S 2 ) ⊆ P ol(S 1 ), then SAT(S 1 ) is polynomial-time reducible to SAT(S 2 ).

Schaefer's classification of SAT(S) follows more or less directly from this result together with Post's lattice of clones. It is worth noting that out of the countably infinite number of Boolean clones, there are just two that corresponds to NP-complete SAT(S) problems. These are the clone I 2 consisting of all projections (i.e. the operations of the form f k i (x 1 , . . . , x k ) = x i ), and the clone N 2 consisting of all projections together with the unary negation function n(0) = 1, n(1) = 0. It is easy to realize that Inv(I 2 ) is the set of all Boolean relations (i.e., BR) and we denote Inv(N 2 ) by IN 2 .

Theorem 4 is not very useful for studying the complexity of SAT problems in terms of their worstcase complexity as a function of the number of variables. The reason is that the reductions do not preserve the size of the instances and may introduce large numbers of new variables. It also seems that the lattice of clones is not fine grained enough for this purpose. For example, 1-in-3-SAT and k-SAT (for k ≥ 3) both correspond to the same clone I 2 .

One way to get a more refined framework is to consider partial operations in Definition 3. That is, we say that R is closed under the (partial) operation f if f applied componentwise to the tuples of R always results in a tuple from R or an undefined result (i.e., f is undefined on at least one of the components). The set of all (partial) operations preserving the relations in S, i.e., the partial polymorphisms of S is denoted pP ol(S) and forms a partial clone. Unlike the lattice of Boolean clones, the lattice of partial Boolean clones consists of an uncountable infinite number of partial clones, and despite being a well-studied mathematical object [START_REF] Lau | Function Algebras on Finite Sets[END_REF], its structure is far from being completely understood.

Before we show that the lattice of partial clones is fine-grained enough to capture the complexity of SAT(S) problems (in terms of the worst-case complexity as a function of the number of variables) we need to present a Galois connection between sets of relations and sets of (partial) functions. Definition 5. For any set S ⊆ BR, the set S consists of all relations that can be expressed (or implemented) using relations from S ∪ {=} (where = denotes the equality relation on {0, 1}), conjunction, and existential quantification. We call such implementations primitive positive (p.p.) implementations. Similarly, for any set S ⊆ BR the set S ∄ consists of all relations that can be expressed using relations from S ∪ {=} and conjunction. We call such implementations quantifier-free primitive positive (q.p.p.) implementations.

Sets of relations of the form S and S ∄ are referred to as relational clones (or co-clones) and partial relational clones, respectively. The lattice of Boolean co-clones is visualized in Figure 2 (see Appendix C). There is a Galois connection between (partial) clones and (partial) relational clones given by the following result. Theorem 6. [START_REF] Bodnarchuk | Galois theory for post algebras[END_REF][START_REF] Bodnarchuk | Galois theory for post algebras[END_REF][START_REF] Geiger | Closed systems of functions and predicates[END_REF][START_REF] Romov | The algebras of partial functions and their invariants[END_REF] Let S 1 and S 2 be constraint languages. Then S 1 ⊆ S 2 if and only if P ol(S 2 ) ⊆ P ol(S 1 ), and S 1 ⊆ S 2 ∄ if and only if pP ol(S 2 ) ⊆ pP ol(S 1 ).

Finally, we show that the complexity of SAT(S), in terms of the worst-case complexity as a function of the number of variables, is determined by the lattice of partial clones.

Theorem 7. Let S 1 and S 2 be finite non-empty sets of Boolean relations. If pP ol(S 2 ) ⊆ pP ol(S 1 ) and

SAT(S 2 ) is solvable in time O(c n ), then SAT(S 1 ) is solvable in time O(c n ).
Proof. Given an instance I of SAT(S 1 ) on n variables we transform I into an equivalent instance I ′ of SAT(S 2 ) on at most n variables. Since S 1 is fixed and finite we can assume that the quantifier-free primitive positive implementations of every relation in S 1 by relations in S 2 has been precomputed and stored in a table (of fixed constant size). Every constraint R(x 1 , . . . , x n ) in I can be represented as

R 1 (x 11 , . . . , x 1n 1 ) ∧ • • • ∧ R k (x k1 , . . . , x kn k ) where R 1 , . . . , R k ∈ S 2 ∪{=} and x 11 , . . . , x kn k ∈ {x 1 , x 2 , . . . , x n }. Replace the constraint R(x 1 , . . . , x n ) with the constraints R 1 , . . . , R k .
If we repeat the same reduction for every constraint in I it results in an equivalent instance of SAT(S 2 ∪ {=}) having at most n variables. For each equality constraint x i = x j we replace all occurrences of x i with x j and remove the equality constraint. The resulting instance I ′ is an instance of SAT(S 2 ) having at most n variables. Also, note that since S 1 is finite, there cannot be more than O(n p ) constraints in total, where p is the highest arity of a relation in

S 1 . Thus, if SAT(S 2 ) is solvable in time O(c n ), then SAT(S 1 ) is solvable in time O(c n ).
⊓ ⊔

The easiest NP-complete SAT problem

In this section we will use the theory and results presented in the previous section to determine the easiest NP-complete SAT(S) problem. Recall that by easiest we mean that if any NP-complete SAT(S) problem can be solved in O(c n ) time, then the easiest problem can be solved in O(c n ) time, too. Following this lead we say that SAT(S) is easier than SAT(S) if SAT(S) is solvable in O(c n ) time whenever SAT(S ′ ) is solvable in O(c n ) time. A crucial step for doing this is the explicit construction of Schnoor and Schnoor [START_REF] Schnoor | New algebraic tools for constraint satisfaction[END_REF] that, for each relational clone X, gives a relation R such that X = {R} and R has a q.p.p. implementation in every constraint language S such that S = X. Essentially, this construction gives the bottom element of the interval of partial relational clones contained in each relational clone. Let {0, 1}-COLS n denote the Boolean relation with arity 2 n that contains all Boolean tuples from 0 to 2 n -1 as columns. Given two relations R = {r 1 , . . . , r n } and Q = {q 1 , . . . , q n } (of the same cardinality), then R • Q denotes the relation that for each r i = (α 1 , . . . , α k ) and q i = (β 1 , . . . , β l ) contains the tuple (α 1 , . . . , α k , β 1 , . . . , β l ). Assume that a set of Boolean functions F and a relation R ⊆ {0, 1} n are given. The F-closure of R, denoted F(R), is the relation R ′ ∈Inv(F ),R⊆R ′ R ′ . Define the extension of a Boolean relation R, R [ext] , to be the relation F(R • {0, 1}-COLS n ). Finally, define the irreduntant core R irr of R [ext] to be the relation obtained when identical columns are removed. In order to unambiguously define R irr , we assume that the first occurrence of each column in R [ext] is kept in R irr . Theorem 8. [START_REF] Schnoor | New algebraic tools for constraint satisfaction[END_REF] Let R be a Boolean relation. Then R [ext] and R irr have q.p.p. implementations in R. Furthermore, any language S such that S = {R} implements R [ext] and R irr via q.p.p. implementations.

We are now in the position to define the easiest NP-complete SAT(S) problem. In the sequel, we use can be defined as

R 1/3 (x 1 , x 2 , x 3 ) ∧ (x 1 = x 4 ) ∧ (x 2 = x 5 ) ∧ (x 3 = x 6 ).
Lemma 9. Let S be a language such that S = BR. Then R irr 1/3 has a q.p.p. implementation in S.

Proof. We first construct the extension of R 1/3 . Since the arity of R 1/3 is 3 we must augment the matrix representation of R 1/3 with the binary numbers from 0 to 7 as columns and close the resulting relation under every polymorphism of BR. However, the projection functions are the only polymorphisms of BR so the relation is left unchanged. Hence,

R [ext] 1/3 = 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1
The irredundant core is then obtained by removing identical columns.

R irr 1/3 = 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 ⊓ ⊔ The relation R irr 1/3 is nothing else than R = = = 1/3
with the two constant columns adjoined, and there is a trivial reduction from SAT(R = = = 1/3 ) to SAT(R irr 1/3 ) introducing only 2 extra variables (one for each constant). Combining this with Theorem 7 and 9 we immediately obtain the following result: Lemma 10. Let S be a language such that S = BR. Then SAT(R = = = 1/3 ) is not harder than SAT(S). We are left with the relational clone IN 2 and need to make sure that the bottom partial relational clone in IN 2 is not (strictly) easier than R = = = 1/3 . We proceed in an analogous manner to the derivation of ).

R = = = 1/3 ,
Lemma 12. SAT(R = = = 1/3 ) is not harder than SAT(R = = = = 2/4
).

Proof. Let φ be an instance of SAT(R = = = 1/3 ) and C = R = = = 1/3 (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) be an arbitrary constraint in φ. Let Y 1 and Y 2 be two global variables. Then the constraint

C ′ = R = = = = 2/4 (x 1 , x 2 , x 3 , Y 1 , x 4 , x 5 , x 6 , Y 2 ) is satisfiable if and only if C is satisfiable, with Y 1 =
1 and Y 2 = 0 (we may assume that Y 1 = 1 since the complement of a satisfiable assignment is also a satisfiable assignment for languages in IN 2 ). If we repeat this reduction for every constraint in φ we get a SAT(R

= = = = 2/4
) instance which is satisfiable if and only if φ is satisfiable. Since the reduction only introduces two new variables, it follows that an O(c n ) algorithm for SAT(R

= = = = 2/4
) can be used to solve SAT(

R = = = 1/3 ) in O(c n ) time, too. ⊓ ⊔
Since S is NP-complete if and only if S = BR or S = IN 2 , Lemma 10 together with Lemma 12 gives that SAT(R = = = 1/3 ) is the easiest NP-complete SAT problem.

Theorem 13. Let S be an NP-complete Boolean language. Then SAT(R = = = 1/3 ) is not harder than SAT(S).

SAT problems with bounded degree

In this section, we investigate the SAT problem where restrictions are placed on the number of occurrences per variable. If x occurs in k constraints then we say that the degree of x is k. If S is a language, then SAT(S)-k is the SAT(S) problem where the degree of each variable is at most k. This restriction is of particular interest since, for all languages S such that SAT(S) is NP-complete, SAT(S)-k is NP-complete for some k.

Theorem 14. [START_REF] Jonsson | Hard constraint satisfaction problems have hard gaps at location 1[END_REF] For any fixed S such that CSP(S) is NP-complete, there is an integer k such that CSP(S)-k is NP-complete.

The most interesting case is when k is the smallest k such that SAT(S)-k is NP-complete. These values are already known for 1-in-3-SAT: for k = 2 it can be reduced to the problem of finding a perfect matching in a graph [START_REF] Istrate | Looking for a version of Schaefer's dichotomy theorem when each variable occurs at most twice[END_REF], but for k = 3 it is NP-complete even for planar instances [START_REF] Moore | Hard tiling problems with simple tiles[END_REF]. It might be expected that the same holds for SAT(R = = = 1/3 ) since it is easier than SAT(R 1/3 ). This is however not the case: SAT(R = = = 1/3 )-k is NP-complete even for k = 2. To prove this we first note that

R = = = 1/3
is not a ∆-matroid relation.

Definition 15. (∆-matroid relation) Let R be a Boolean relation and x, y, x ′ be Boolean tuples of the same arity. Let d(x, y) be the binary difference function between x and y. Then x ′ is a step from x to y if d(x, x ′ ) = 1 and d(x, y) = d(x ′ , y)

+ d(x, x ′ ). R is a ∆-matroid relation if it satisfies the following axiom: ∀x, y ∈ R ∀x ′ .(x ′ is a step from x to y) → (x ′ ∈ R ∨ ∃x ′′ ∈ R which is a step from x ′ to y). Lemma 16. R = = = 1/3 is not a ∆-matroid relation.
Proof. Let x = 001110 and y = 010101. These are both elements in

R = = = 1/3 . Let x ′ = 000110. Then d(x, x ′ ) = 1, d(x, y) = 4 = d(x, x ′ ) + d(x ′ , y) = 1 + 3 = 4, whence x ′ is a step from x to y. For R = = = 1/3
to be a ∆-matroid relation either x ′ ∈ R = = = 1/3 , or there exists a x ′′ which is a step from x ′ to y. Since neither of the disjuncts are true, it follows that R = = = 1/3 is not a ∆-matroid relation.

⊓ ⊔

The hardness result then follows from Theorem 3 in Dalmau and Ford [START_REF] Dalmau | Generalized satisfiability with limited occurrences per variable: A study through delta-matroid parity[END_REF], which states that SAT(S)-2 is NP-complete if S contains a relation that is not ∆-matroid.

Theorem 17. SAT(R = = = 1/3 )-2 is NP-complete.
6 The exponential-time hypothesis

Even though R = = = 1/3
is the easiest NP-complete language, we cannot hope to prove or disprove that SAT(R = = = 1/3 ) or SAT(R = = = 1/3 )-2 is solvable in polynomial time since this would settle the P = NP question. A more assailable question is if the problem can be solved in sub-exponential time. If yes, then we are none the wiser; but if no, then P = NP. As a tool for studying sub-exponential problems, Impagliazzo et. al [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] proved a sparsification lemma for k-SAT. Intuitively, the process of sparsification means that a SAT instance with a large number of constraints can be expressed as a disjunction of instances with a comparably small number of constraints. We prove that sparsification is possible not only for k-SAT, but between all NP-complete, finite languages, and use this to prove that SAT(R = = = 1/3 )-2 is subexponential if and only if the exponential-time hypothesis is false. Due to sparsification we can also prove that all NP-complete languages are sub-exponential if and only if one NP-complete language is sub-exponential (and that this holds also in the degree-bounded case), which is a significant refinement of Impagliazzo et. al's result when restricted to finite Boolean languages.

Preliminaries

There has been a stride in constructing faster exponential algorithms for NP-complete problems. A natural question to ask is whether there exists a constant c such that a problem is solvable in O(c n ), but not for any c ′ smaller than c. Problems without such a sharp limit are said to be sub-exponential. Definition 18. A language S is sub-exponential if SAT(S) is solvable in O(2 ǫn ) for all ǫ > 0.

We now need a class of reductions that relates languages based on their sub-exponential complexity. Reductions based on q.p.p. definitions are however to precise to fully encompass this since they preserve exact complexity -a reduction should be able to introduce new variables as long as the resulting instance can be solved in sub-exponential time. We introduce linear variable reductions, which should be compared to the more complex but general class of SERF-reductions from Impagliazzo et. al [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF].

Definition 19. Let S and S ′ be two finite languages and φ a SAT(S) instance with n variables. A total function f from SAT(S) to SAT(S ′ ) is a many-one linear variable reduction, or an LV-reduction, if:

1. φ is satisfiable if and only if f (φ) is satisfiable, 2. the number of variables in f (φ), n ′ , is only increased by a linear amount, i.e. there exists a fixed constant C such that n ′ ≤ Cn, and 3. f (φ) can be computed in O(poly(n)) time.

The point of the definition is that an LV-reduction between two languages preserves sub-exponentiality. Hence, if SAT(S) is sub-exponential and we know that SAT(S ′ ) is LV-reducible to SAT(S), then SAT(S ′ ) is sub-exponential as well. The proof is straightforward and is included in Appendix B.

Lemma 20. Let S and S ′ be two finite languages such that SAT(S) is sub-exponential. If there exists an LV-reduction from SAT(S ′ ) to SAT(S), then SAT(S ′ ) is sub-exponential.

Let S and S ′ be two finite languages such that S ⊆ S ′ . We can then reduce SAT(S) to SAT(S ′ ) by replacing each constraint from S by its equivalent implementation in S ′ . Such a reduction would need C • m new variables, where C is a constant that only depends on S ′ , and m the number of constraints in the instance. If m is large compared to the number of variables, n, this would however require more than a linear amount of new variables. We can therefore only prove that LV-reductions exist for classes of problems where m is linearly bounded by the number of variables. The proof is in Appendix B.

Lemma 21. Let S and S ′ be two finite languages such that SAT(S) and SAT(S ′ )-k are NP-complete for some k. If S ′ ⊆ S , then SAT(S ′ )-k is LV-reducible to SAT(S).

This does not imply that there exists LV-reductions between SAT(S) and SAT(S ′ ) for all NPcomplete languages S and S ′ since these problems are not degree-bounded, but it is a useful tool in the sparsification process. Definition 22. Let S and S ′ be two finite languages. We say that S is sparsifiable into S ′ if, for all ǫ > 0 and for all SAT(S) instance φ (with n variables), φ can be expressed by a disjunctive formula t i=1 φ i , where:

1. φ is satisfiable if and only if at least one φ i is satisfiable, 2. k is a constant that only depends on ǫ, S and S ′ , 3. φ i is a SAT(S ′ )-k instance, 4. t ≤ 2 ǫn , and 5. t i=1 φ i can be computed in O(poly(n) • 2 ǫn ) time. Note that nothing in the definition says that S and S ′ cannot be the same language. If so, we simply say that S is sparsifiable. Impagliazzo et. al [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] prove the following for k-SAT. Lemma 23. (sparsification lemma for k-SAT) k-SAT is sparsifiable.

General sparsification

Recall from Section 2 that we use Γ k SAT and Γ k NAE to denote the languages of k-SAT and NAE-k-SAT respectively. In order to prove that sparsification is possible between all NP-complete, finite languages we first prove that Γ k NAE is sparsifiable, and then that all NP-complete languages in BR and IN 2 can be sparsified by reducing them to either

Γ k SAT or Γ k NAE . Lemma 24. (sparsification lemma for NAE-k-SAT) Γ k NAE is sparsifiable. Proof. Let φ be a SAT(Γ k NAE ) instance with n variables. If γ k NAE (x 1 , . . . , x k
) is a constraint from φ it can be verified that it is satisfiable if and only if γ k SAT (x 1 , . . . , x k ) ∧ γ k SAT (¬x 1 , . . . , ¬x k ) is satisfiable. We can therefore form an equivalent SAT(Γ k SAT ) instance ψ by adding the complement of every γ k NAEconstraint. By the sparsification lemma for k-SAT, it then follows that ψ can be sparsified into the disjunctive formula t i=1 ψ i . We must now prove that each ψ i is reducible to an equivalent SAT(Γ k NAE )l instance, for some constant l that does not depend on n.

For simplicity, we shall first reduce each disjunct to SAT(Γ k+1 NAE ). For each constraint γ k SAT (x 1 , . . . , x k ) ∈ ψ i we let γ k+1 NAE (x 1 , . . . , x k , X) be the corresponding γ k+1 NAE -constraint, where X is a fresh variable common to all constraints. Let ψ ′ i be the resulting SAT(Γ k+1 NAE ) instance. Then ψ i is satisfiable if and only if

ψ ′ i is satisfiable: if ψ i is satisfiable, then ψ ′ i is satisfiable with X = 0; if ψ ′
i is satisfiable we may assume that X = 0 since the complement of each valid assignment is also a valid assignment. But then each constraint has at least one literal that is not 0, by which it follows that ψ i must be satisfiable. Since ψ was sparsified, the degree of the variables in ψ i is bounded by some constant C. Hence X cannot occur in more than C • n constraints. We now prove that the degree of X can be reduced to a constant value. Since Γ k+1 NAE = IN 2 we can implement an equality relation that has the form Eq(x, y) ≡ ∃z 1 , . . . , z T .θ, where θ is a conjunction of constraints over Γ k+1 NAE . Let V denote the highest degree of any variable in θ. We may without loss of generality assume that 2V < C since we can otherwise adjust the ǫ-parameter in the sparsification process.

To decrease the degree of X we introduce the fresh variables X ′ 1 , . . . , X ′ W in place of X and the following chain of equality constraints: Eq(X, X

′ 1 ) ∧ Eq(X ′ 1 , X ′ 2 ) ∧ . . . ∧ Eq(X ′ W -1 , X ′ W ). Let the resulting formula be ψ ′′ i . Then ψ ′ i is satisfiable if and only if ψ ′′ i is satisfiable since X = X ′ 1 = . . . = X ′
W in all models. Then W = C•n C-2V new variables are needed since each X ′ i can occur in C -2V additional constraints. Since each equality constraint requires T variables the whole equality chain requires

⊓ ⊔

The proof of the following auxiliary lemma can be found in Appendix B.

Lemma 25. Let S be a finite language such that S ⊆ IN 2 and let S ′ be a finite language such that S ′ ⊆ BR. Then, SAT(S) is LV-reducible to SAT(Γ k NAE ), for some k dependent on S, and SAT(S ′ ) is LV-reducible to SAT(Γ k ′ SAT ), for some k ′ dependent on S ′ . Since a language S is NP-complete if and only if S = BR or S = IN 2 , we can now prove that sparsification is possible between all finite NP-complete languages. For case [START_REF] Bodirsky | Non-dichotomies in constraint satisfaction complexity[END_REF], assume that S = S ′ = IN 2 . Let p denote the highest arity of a relation in S. If φ is a SAT(S) instance with n variables it can be reduced to a SAT(Γ p NAE ) instance φ ′ with the same number of variables by Lemma 25. Then, according to the sparsification lemma for NAE-k-SAT, there exists a disjunction of SAT(Γ k NAE )-l formulas such that φ ′ = t i=1 φ i . Since S ′ = IN 2 , each φ i can be implemented as a conjunction of constraints over S ′ with a linear amount of extra constraints and variables. Let φ ′ i denote each such implementation. Then φ ′ i is an instance of SAT(S ′ )-l ′ , for some l ′ determined by l and S ′ . Hence SAT(S) is sparsifiable into SAT(S ′ ).

Case ( 2) is analogous to case (1) but with Γ k SAT instead of Γ k NAE . Case (3) follows from case (2) since all finite languages are sparsifiable into Γ k SAT by Lemmas 23 and 25. For case (4), assume that S = BR and S ′ = IN 2 . Let p denote the relation with the highest arity in S. If φ is a SAT(S) instance with n variables it can be LV-reduced to a SAT(Γ p SAT ) instance φ ′ by lemma 25. Since Γ k SAT is sparsifiable there exists a disjunction such that φ ′ = t i=1 φ i . By recapitulating the steps from Lemma 24 we can then reduce each φ i to a SAT(Γ k+1 NAE )-l instance φ ′ i . Then, since S ′ = IN 2 , each φ ′ i can be implemented as a conjunction of constraints over S ′ such that no variable occurs in more than l ′ constraints, where l ′ is determined by l and S ′ .

⊓ ⊔ Santhanam and Srinivasan [START_REF] Santhanam | On the limits of sparsification[END_REF] have shown that the unrestricted SAT problem (which corresponds to an infinite constraint language) does not admit sparsification to arbitrary finite NP-complete languages. Consequently, it is a necessary condition that the languages in Theorem 26 are indeed finite.

SAT and the exponential-time hypothesis

The exponential-time hypothesis states that k-SAT is not sub-exponential [START_REF] Impagliazzo | On the complexity of k-SAT[END_REF] for k ≥ 3. If one assumes that P = NP, then this statement is plausible since it enforces a limit on the time complexity of exponential algorithms. A problem that is sub-exponential if and only if k-SAT is sub-exponential is said to be ETH-hard. Impagliazzo et. al prove that many NP-complete problems such as k-colorability, clique and vertex cover are ETH-hard. An ETH-hard problem has the property that it is sub-exponential if and only if all problems in SNP are sub-exponential. In this section we prove that both SAT(R = = = 1/3 ) and SAT(R = = = 1/3 )-2 are ETH-hard, and this implies that all finite, NP-complete languages are ETH-hard even for degree-bounded instances. This result does not exclude the possibility that there exist an extremely simple NP-complete problem that is not ETH-hard, it seems that such a problem is unlikely to reside in the Boolean domain.

Theorem 27. The following statements are equivalent:

1. The exponential-time hypothesis is false.

SAT(R

= = = 1/3 )-2 is sub-exponential. 3. SAT(R = = = 1/3
) is sub-exponential. 4. For every NP-complete and finite language S, SAT(S) is sub-exponential. 5. For every NP-complete and finite language S, SAT(S)-k is sub-exponential for every k. 6. There exists an NP-complete and finite language S such that SAT(S) is sub-exponential. 7. There exists an NP-complete and finite language S such that SAT(S)-k is sub-exponential for all k.

Proof. We will prove that 1 =⇒ . . . =⇒ 7 =⇒ 1 and hence that all statements are equivalent.

1 =⇒ 2: If the exponential-time hypothesis is false then k-SAT is sub-exponential. But then

R = = = 1/3
must also be since it is the easiest NP-complete language. This immediately implies that SAT(

R = = = 1/3 )-2 is sub-exponential. 2 =⇒ 3: We must prove that SAT(R = = = 1/3 ) is sub-exponential if SAT(R = = = 1/3 )-2 is sub-exponential. Let φ be a SAT(R = = =
1/3 ) instance with n variables. Due to Theorem 26 there exists a disjunction of SAT(R = = = 1/3 )-l instances such that φ = t i=1 φ i , where l is a constant that does not depend on n. Next assume that x is a variable in φ i that occurs in 2 < k ≤ l constraints. Since this is not a valid SAT(R = = = 1/3 )-2 instance the degree of x must be lowered to 2. Call two variables in an R = = = 1/3 -constraint complementary if one occurs in position i = 1, 2 or 3, and the other in position i + 3. It is easily verified that variables fulfilling this constraint are indeed each other's complement. Let C 1 , . . . , C k be an enumeration of the constraints that contains x. Without loss of generality we may assume that x always occur in position 1 and that it has a single complementary variable x ′ which occurs in position 4 in the same k constraints. For each three constraints,

C i-1 = R = = = 1/3 (x, y i-1 , z i-1 , x ′ , y ′ i-1 , z ′ i-1 ), C i = R = = = 1/3 (x, y i , z i , x ′ , y ′ i , z ′ i ), and
C i+1 = R = = = 1/3 (x, y i+1 , z i+1 , x ′ , y ′ i+1 , z ′ i+1
), we can then lower the degree of x and x ′ by introducing the constraints C ′ i-1 , C ′ i , and C ′ i+1 , which we define such that

C ′ i-1 = R = = = 1/3 (x, y i-1 , z i-1 , x ′ , y ′ i-1 , z ′ i-1 ), C ′ i = R = = = 1/3 (x, y i , z i , x ′′ , y ′ i , z ′ i ), and
C ′ i+1 = R = = = 1/3 (x ′′′ , y i+1 , z i+1 , x ′′ , y ′ i+1 , z ′ i+1 ).
Here, x ′′ and x ′′′ are fresh variables. Since the new variables occur in the same complementary positions it follows that x = x ′′′ = ¬x ′ = ¬x ′′ , and that C i-1 , C i , C i+1 are satisfiable if and only if

C ′ i-1 , C ′ i , C ′ i+1 are satisfiable.
If the procedure is repeated iteratively for all C 1 , . . . , C k the degree of x or any newly introduced variable in C ′ 1 , . . . , C ′ k is at most 2. Let φ ′ i denote the formula obtained when the procedure is repeated for all variables occurring k times, 2 < k ≤ l. The total number of variables needed is then bounded by the linear expression l ′ n, where l ′ is a constant determined by l.

Since no variable in φ ′ i occurs in more than two constraints, we can then use a sub-exponential algorithm for SAT(R = = = 1/3 )-2, and answer yes if and only if at least one

φ ′ i is satisfiable. Hence SAT(R = = = 1/3 ) is sub-exponential if SAT(R = = = 1/3 )-2 is sub-exponential. 3 =⇒ 4: Assume that R = = = 1/3
is sub-exponential. Let S be an arbitrary finite language and φ be an instance of SAT(S). According to the general sparsification result (Theorem 26), φ can be sparsified into t i=1 φ i , where each φ i is an instance of SAT(R = = = 1/3 )-l. But then we can simply use a sub-exponential algorithm for SAT(R = = = 1/3 ) and answer yes if and only if at least one of the disjuncts is satisfiable. 4 =⇒ 5: Trivial.

5 =⇒ 6: Assume that SAT(S) is NP-complete and that SAT(S)-k is sub-exponential for every k. Let φ be a SAT(S) instance. Then according to Theorem 26, there exists a disjunction t i=1 φ i of SAT(S)-l formulas, for some constant l. Since SAT(S)-k is sub-exponential for every k we can use a sub-exponential algorithm for SAT(S)-l and answer yes if and only if at least one of the disjuncts is satisfiable.

6 =⇒ 7: Trivial. 7 =⇒ 1: Assume that SAT(S) is NP-complete and that SAT(S)-k is sub-exponential for all k. According to Theorem 26), any instance of SAT(Γ k SAT ) can be expressed as a disjunction of SAT(S)-l instances for some constant l. But since SAT(S)-k is sub-exponential for all k we can simply use a sub-exponential algorithm for SAT(S)-l and answer yes if and only if at least one of the disjuncts is satisfiable.

⊓ ⊔

Research directions and open questions

We will now discuss some research directions and pose some open questions. After having shown that SAT(R = = = 1/3 ) is the easiest NP-complete SAT problem, it is tempting to try to determine bounds on its time complexity. We are currently working on a branch-and-bound algorithm for this problem and preliminary results show that this algorithm runs in O(α n ) time where α ≈ 1.05. We are fairly convinced that the time complexity can be significantly lowered by a more careful analysis of the algorithm.

We have proved that SAT(S) is sub-exponential if and only if SAT(S)-k is sub-exponential for all k. This result is inconclusive since it does not rule out the possibility that a language is sub-exponential and NP-complete for some k, but that the sub-exponential property is lost for larger values. Hence, it would be interesting to (dis)prove that SAT(S) is sub-exponential if and only if there exists some k such that SAT(S)-k is NP-complete and sub-exponential. This holds for SAT(R = = = 1/3 ) so it does not seem impossible that the result holds for all languages. We also remark that bounding the degree of variables is not the only possible structural restriction: many attempts at establishing structurally based complexity results are based on the tree-width (or other width parameters) of some graph representation of the constraints, cf. [START_REF] Dalmau | Constraint satisfaction, bounded treewidth, and finitevariable logics[END_REF][START_REF] Grohe | The complexity of homomorphism and constraint satisfaction problems seen from the other side[END_REF]. A particularly interesting example is Marx's [START_REF] Marx | Can you beat treewidth?[END_REF] result that connects ETH with structural restrictions: if ETH holds, then solving the CSP problem for instances whose primal graph has treewidth k requires n Ω(k/ log k) time.

A natural continuation of this research is to generalize the methods in Section 3 to other problems. Generalizing them to constraint satisfaction problems over finite domains appears to be effortless, and such a generalisation would give us a tool for studying problems such as k-colourability and its many variations. Lifiting the results to infinite-domain constraints appears to be more difficult, but it may be worthwhile: Bodirsky and Grohe [START_REF] Bodirsky | Non-dichotomies in constraint satisfaction complexity[END_REF] have shown that every computational decision problem is polynomial-time equivalent to such a constraint problem. Hence, this may lead to general methods for studying the time complexity of computational problems. Another interesting generalisation is to study problems that are not satisfiability problems, e.g. enumeration problems, counting problems, and non-monotonic problems such as abduction and circumscription.

As we have already mentioned, a drawback of Theorem 7 is that the structure of the Boolean partial clone lattice is far from well-understood (and even less well-understood when generalized to larger domains). Hence, it would be interesting to look for lattices that have a granularity somewhere in between the clone lattice and the partial clone lattice. One plausible candidate is the lattice of frozen partial clones that were introduced in [START_REF] Nordh | Frozen Boolean partial co-clones[END_REF]. A frozen implementations is a primitive positive implementation where we are only allowed to existentially quantify over variables that are frozen to a constant (i.e., variables that are constant over all solutions). For more details about frozen partial clones (e.g., the Galois connection between frozen partial clones and frozen partial relational clones), we refer the reader to [START_REF] Nordh | Frozen Boolean partial co-clones[END_REF]. We remark that the complexity of SAT(S) is determined by the frozen partial clones and that the lattice of frozen partial clones is indeed coarser than the lattice than the lattice of partial clones as there are examples of infinite chains of partial clones that collapse to a single frozen partial clone [START_REF] Haddad | Infinite chains of partial clones containing all selfdual monotonic partial functions[END_REF][START_REF] Nordh | Frozen Boolean partial co-clones[END_REF].

A Additional proofs for section 4

Proof. (Lemma 11) Let R NAE be not-all-equal-SAT as defined in Section 2 and recall that R NAE = IN 2 . By Theorem 8 it is enough to show that the irreduntant core R irr of R

[ext] NAE can implement R = = = = 2/4
with a p.p.q implementation. Since the cardinality of R NAE is 6, R irr will have arity 2 6 = 64, consist of 12 tuples where the columns of the six first tuples are the binary numbers from 0 to 63, and the six last tuples the complements of the six first. The matrix representation is therefore as follows.

R irr =            0 0 • • • 1 1 0 0 • • • 1 1 0 0 • • • 1 1 0 0 • • • 1 1 0 0 • • • 1 1 0 1 • • • 0 1 . . . . . . . . . . . . 1 0 • • • 1 0           
Let x 1 , . . . , x 64 denote the columns in the matrix and the variables in the relation. We must now prove that R irr can implement R = = = = 2/4 with a p.p.q implementation. Note that x 1 and x 2 only differ in one row. If we identified x 1 and x 2 we would therefore get a relation where that tuple was removed. But since

R = = = =       0 0 0 1 1 1 1 1 1 0 0 0                  
Therefore identifying x 1 and x 8 will remove rows 4, 5, 6 and 10, 11, 12 from R irr . If we then collapse identical columns the resulting matrix will be:

       0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0       

It can be verified that this relation is nothing else than a rearranged version of R

= = = = 2/4
. Hence, since S can p.p.q. define R irr , which in turn can p.p.q. define R

= = = = 2/4
, it follows that S can also p.p.q. define R

= = = = 2/4 .
⊓ ⊔

B Additional proofs for section 6

Proof. (Lemma 20) Assume that SAT(S ′ ) can be solved in time O(c n ) but not in O(c nǫ ) for any 0 < ǫ < 1. Since SAT(S) is sub-exponential it can be solved in time O(c ǫn ) for all ǫ > 0. Assume that the LV-reduction from SAT(S ′ ) to SAT(S) implies that the resulting instance contains at most C • n variables where C is a constant. This will make SAT(S ′ ) solvable in time O(c (C•n)ǫ ) for all ǫ > 0 which contradicts the assumption.

⊓ ⊔

Proof. (Lemma 21) Let φ be a SAT(S ′ )-k-instance with n variables. Since each variable can occur in at most k constraints there cannot be more than n • k constraints in total. Each such constraint is of the form R(x 1 , . . . , x i ) where R ∈ S ′ . By assumption R can then be expressed as a conjunction of constraints over S ∪ {=} with a set of existentially quantified variables: ∃y 1 , . . . , y j . ψ(Y ), where each ψ ∈ S ∪ {=} and Y ⊆ {x 1 , . . . , x i } ∪ {y 1 , . . . , y j }.

Hence the number of extra variables for each constraint depends on the relations from S ′ . Let t denote the largest amount of variables that is required for implementing a constraint. In the worst case the total amount of new variables in the reduction is then (n • k)t, which is linear with respect to n since k and t are fixed values.

Since the reduction only increases the amount of variables with a linear factor it is indeed an LVreduction, which concludes the lemma. If R(x 1 , . . . , x p ) is a constraint in φ, then it can be expressed by the SAT(Γ p NAE ) formula ψ 1 ∧ . . . ∧ ψ N , where each ψ i = γ p NAE (y 1 , . . . , y p ), and y j = x j if b i,j is 0, and y j = ¬x j if b i,j is 1. Each such constraint represents one of the excluded tuples in E 1 and one of the excluded tuples in E 2 , and as such the formula as a whole is satisfiable if and only if R(x 1 , . . . , x p ) is satisfiable. The same procedure can be repeated for all the other relations in S. Moreover, since no extra variables are introduced and the number of new constraints is bounded by S, the reduction is an LV-reduction.

Let R ∈ S ′ be a relation with arity p and φ an instance of SAT(S ′ ) with n variables. By definition, R = {0, 1} p E, where E is a set of p-ary tuples over {0, 1} that describes the excluded tuples in the relation.

Let |E| = N and e 1 , . . . , e N ∈ E be an enumeration of its elements. Let e i = (b i,1 , . . . , b i,p ), b i,j ∈ {0, 1}.

If R(x 1 , . . . , x p ) is a constraint in φ, then it can be expressed by the SAT(Γ p SAT ) formula φ 1 ∧ . . . ∧ φ N , where each φ i = γ p SAT (y 1 , . . . , y p ), and y j = x j if b i,j is 0, and y j = ¬x j if b i,j is 1. Each constraint represents exactly one of the excluded tuples in R, and as such the formula as a whole is satisfiable if and only if R(x 1 , . . . , x p ) is satisfiable. The same prodecure can be repeated for all the other relations in S. Moreover, since no extra variables are introduced and the number of new constraints are bounded by S ′ , the reduction is an LV-reduction.

⊓ ⊔

D 2 L L 1 L 0 L 2 L 3 V V 1 V 0 V 2 E E 0 E 1

Example 2 .

 2 Let R NAE be the following ternary relation on {0, 1}: R NAE = {0, 1} 3 \{(0, 0, 0), (1, 1, 1)}. It is easy to see that the well known NP-complete problem NOT-ALL-EQUAL 3-SAT can be expressed as SAT({R NAE }).

  b 1 . . . b k as a shorthand for the tuple (b 1 , . . . , b k ). Define the relation R 1/3 = {001, 010, 100} and note that SAT({R 1/3 }) corresponds to the 1-in-3-SAT problem. The relation R = = = 1/3 = {001110,010101,100011} is formed by taking R 1/3 and adding the negation of each of the columns, i.e., R = = = 1/3

4 =

 4 and define a maximal extended relation which is then pruned of superfluous columns. Let R NAE be defined as in Section 2. Analogously to the relation R = = = 1/3 in BR, we consider the relation R = = = = 2/{00111100,01011010,10010110, 11000011,10100101, 01101001} in IN 2 . The proof can be found in Appendix A. Lemma 11. Let S be a language such that S = IN 2 . Then S implements R = = = = 2/4 via a q.p.p. implementation. Both R = = = 1/3 and R = = = = 2/4 can be viewed as candidates for the easiest NP-complete languages. In order to prove that R = = = 1/3 is not harder than R = = = = 2/4 we must give a size-preserving reduction from SAT(R = = = 1/3 ) to SAT(R = = = = 2/4

Theorem 26 .

 26 (sparsification between all finite NP-complete languages) Let S and S ′ be two finite languages such that SAT(S) and SAT(S ′ ) are NP-complete. Then, SAT(S) is sparsifiable into SAT(S ′ ).Proof. There are a few different cases depending on which co-clones that are generated by S and S ′ : (1) S = S ′ = IN 2 , (2) S = S ′ = BR, (3) S = IN 2 , S ′ = BR, and (4) S = BR, S ′ = IN 2 .

  Lemma 25) Let φ be an instance of SAT(S) with n variables, and let R ∈ S be a relation with arity p. By definition, R = {0, 1} p E, where E is a set of p-ary tuples over {0, 1} that describes the excluded tuples in the relation. Since all relations in S must be closed under complement we can partition E into E 1 and E 2 where each tuple in E 2 is the complement of a tuple in E 1 .Let|E 1 | = |E 2 | = Nand e 1 , . . . , e N be an enumeration of the elements in E 1 . Let e i = (b i,1 , . . . , b i,p ), b i,j ∈ {0, 1}.

2 N 2 NFig. 1 .Fig. 2 .

 2212 Fig. 1. The lattice of Boolean clones.

  C•n•T C-2V variables which is linear with respect to n since T , C and V are constants. But since Γ k+1 NAE = Γ k NAE = IN 2 and no variable occurs more than C times we can use Lemma 21 and LV-reduce ψ ′′ i to an equivalent SAT(Γ k NAE ) instance φ i . Since all variables in ψ ′′ i are degree bounded by C there exists a constant l determined by C and Γ k NAE such that no variable in φ i occurs in more than l constraints, i.e. φ i is an instance of SAT(Γ k NAE )-l. It now follows that φ is satisfiable if and only if at least one of the disjuncts φ i is satisfiable. Hence Γ k NAE is sparsifiable.

Acknowledgments

We thank Magnus Wahlström for helpful discussions on the topic of this paper.


Gireg Desmeulles

Vincent Ferec

Pascal Redou

Vincent Rodin

Alain-Claude Roudot
email: alain-claude.roudot@univ-brest.fr

A new PBTK modelling method based on multi interactions paradigm

Keywords: exposure, multi interactions modeling, multi agent simulation, toxicology, PBTK

One of the problems not clearly solved nowadays in food toxicology, is the evaluation of internal exposure to natural chemical contaminants. The worst solution is based on the concept that internal and external exposure are of the same level. One can go through this concept by considering biomarkers which can be used to calculate the inner contamination. Another solution is the use of a PBTK simulation method (Physiologically-Based Toxico-Kinetics). This method allows the knowledge of distribution of the contaminant over all the organs and their evolution in time. Unfortunately, the modeling and simulation processes are very hard to implement and use. The use of a technology issued from virtual modeling shows a good opportunity of developing a user interface easy to use for biologists. This interface is based on the multi interactions paradigm which is an evolution of the multi agent simulations.

INTRODUCTION

Food toxicology is a science which is interested in the analysis of bad consequences of eating on health. For new chemical components of food, a toxicological study is made which allows the determination of a usable limit of this chemical in food in order to be sure that no adverse consequences could occur. For natural components, it is impossible to decide in such a way and so a method of evaluation of the internal exposure is needed. For some natural components biomarkers are well known in blood or urine for instance. In those cases, the knowledge of the quantity of biomarkers allows the determination of inner exposure.

Unfortunately, for most chemicals no biomarker is known and the only solution is to mathematically calculate that exposure. In order to do this the PBTK modeling and simulation method is considered as the best current solution (US EPA, 2006). However, this method is very difficult to use and few results are obtained because of two main reasons [START_REF] Krishnan | Physiologically based Pharmacokinetic and Toxicokinetic models[END_REF]. The first one is that numerous parameters are needed for each chemical and it is not very easy to determine them. The second problem is that this method was developed by computer scientists and mathematicians and need a large mathematical and numerical background to be used in good conditions. If solutions are generally found for the first problem, consisting in the comparisons of the chemical under analysis with other chemicals of the same family for instance, no real progress was made for the second problem, which needs to move from a mathematical paradigm to another one. This last one could be the use of virtuality.

PBTK MODELLING

Pharmacokinetics involves the study of the time course of the parent chemical or metabolite concentrations or amounts in biological fluids, tissues, and excreta and the construction of mathematical models to interpret such data [START_REF] Wagner | History of pharmacokinetics[END_REF]. The time course of the concentration of a chemical or its metabolite in biota is determined by the rate and extent of absorption, distribution, metabolism, and excretion (ADME). The pharmacokinetics or ADME of a substance determines the delivered dose or the amount of chemical available for interaction in the tissues. Relating adverse response observed in biota to an appropriate measure of delivered dose (e.g., concentration of the toxic chemical in the target tissue) rather than administered dose or exposure concentration is likely to improve the characterization of many dose-response relationships. Adverse tissue responses are more directly and closely related to the internal target tissue dose of the toxic moiety than to the concentration of the parent chemical in the environment. Therefore, the scientific basis of, and confidence in, risk assessments are enhanced when they are supported by estimates of the internal tissue dose. Data for the internal tissue dose levels, however, are generally not available, and the relationship between external and internal dose may not be easily resolved. PBTK models provide a means of estimating the internal dose for many different exposure regimens based on what is known about the physiology of the test species and the chemical of interest. PBTK models reduce the uncertainty in dose-response and exposure assessment

MULTI INTERACTIONS PARADIGM

A classical PBTK model is a compartment model, each representing organs or group of organs. The flows between compartments represent the veins and arteries. This kind of description can be computed in terms of a multi-agent model. Each organ (or group of organ) being an agent. In a multi agent model, each agent has three functions: observing his neighborhood, deciding if something has to be done, and applying that decision. Then, for instance, if you model a colony of individuals interacting, each individual is an agent with its own behaviour. This method of modeling has a great advantage in programming because each agent is independent and can have its own functionalities. It is easy to understand the program and to modify it, because all algorithms are simples. The complexity of the global behaviour comes from the multiplication of agents. Classically one has an individual-based vision of the world, or in our area an organ-vision of the human body. That means that the important point is the description of these organs, and then, in order to link these isolated parts, one describes the possible interactions. Then, interactions between two organs have to be described in these two organs. Anyway, in a PBTK model, what is really important to model is not the state of each organ but the evolution of the chemical concentrations. These concentrations change because of the flows between the compartments. Then the important elements are these flows, which are called interactions in this new paradigm. That is the reason why we propose a multi-interactions model. In this case the main elements to be modeled are the interactions between organs, these last ones being described only through their state changes due to the flows variations (the interactions). A theoretical description of this paradigm can be found in [START_REF] Desmeulles | In virtuo experiments based on the multi-interaction system framework : the RéISCOP meta-model[END_REF].

TOXCIN PROGRAM

The ToxCin program is an application of the multiinteractions paradigm to PBTK modelling. In the application of this concept, we use different elements:

-The phenomenon, which can create new interactions when it is justified. The interaction is a specific manifestation of the phenomenon. Interaction is classically called flow.

-The organization is defined as a set of phenomena and interactions. Practically, each one corresponds to one organ.

-The components are compartments corresponding to concentrations, volumes and parameters necessary for simulation.

-The influences are mathematical element allowing the creation of links between two components. For instance, on fig1, the two biggest rectangles are two organizations representing organs. Inside these elements small rectangles are components corresponding to concentrations of the chemical and volume. The circle inside organization 2 is an interaction representing metabolization in that organ. The circle situated outside the organizations is an interaction representing the flow of chemical betwwen the two organs. All these elements are defined by values and equations such as chosen on fig2 ToxCin was applied on an example of dioxin exposure through inhalation already published [START_REF] Bois | Modélisation toxicocinétique de la concentration sanguine de 2,3,7,8-tétrachloropdioxine après ingestion chez la femme[END_REF], in order to evaluate its possibilities and limitations. The model is shown on fig3. Comparisons between the simulation results between the classical PBTK modelling using MATLAB programming, and this new methods show good agreement. The avantage of Toxcin is its programming simplicity only based on a visual method and not necessitating any knowledge in programming. Anyway at this time there is no help for defining the equations needed or for final visualization of the variations of chemicals concentrations in the organs analysed.

CONCLUSION

The current model is yet under tests but it can do classical PBTK modeling i.e. calculating the variation of concentrations of chemicals amongst the different organs or in the blood. Its main current interest is the interface which is totally graphical and can be used by everybody after a short-time training (Fig 1 and3). The only elements to enter are the biological and chemical constants (which could be taken from scientific litterature) and (for the moment) the transfer equations in the interactions and influence. Its further evolutions will be in the possibilities of working together on the chemicals and its metabolites, in adding a method in order to take into account the parameters variabilities and in a better user interface with an help in writing the different mathematical equations, and better results publishing properties.

Figure 1 :

 1 Figure 1: example of a simple model showing two organizations with flow between these ones and a metabolization.

Figure 2 :

 2 Figure 2: Example of a defining window for an influence in the dioxin model of fig3.

Figure 3 :

 3 Figure 3: The PBTK model created by ToxCin, concerning the women exposure to dioxins