Florent Capelli
email: florent.capelli@univ-lille3.fr

Yann Strozecki
email: yann.strozecki@uvsq.fr

On the Complexity of Enumeration

Keywords: enumeration, incremental time, polynomial delay, structural complexity, exponential time hypothesis

We investigate the relationship between several enumeration complexity classes and focus in particular on problems having enumeration algorithms with incremental and polynomial delay (IncP and DelayP respectively). We show that, for some algorithms, we can turn an average delay into a worst case delay without increasing the space complexity, suggesting that IncP 1 = DelayP even with polynomially bounded space. We use the Exponential Time Hypothesis to exhibit a strict hierarchy inside IncP which gives the first separation of DelayP and IncP. Finally we relate the uniform generation of solutions to probabilistic enumeration algorithms with polynomial delay and polynomial space.

Introduction

An enumeration problem is the task of listing a set of elements, usually corresponding to the solutions of a search problem, such as enumerating the spanning trees of a given graph or the satisfying assignments of a given formula. One way of measuring the complexity of an enumeration algorithm is to evaluate how the total time needed to compute all solutions relates with the size of the input and with the size of the output, as the number of solutions may be exponential in the size of the input. Therefore, a problem is considered tractable and said to be output polynomial when it can be solved in polynomial time in the size of the input and the output. This measure is relevant when one wants to generate and store all elements of a set, for instance to constitute a library of interesting objects, as it is often done in biology or chemistry [START_REF] Barth | Efficient generation of stable planar cages for chemistry[END_REF].

Another application is to use enumeration algorithms to compute optimal solutions by generating them all or to compute statistics on the set of solutions such as evaluating its size. If this set is too large, it can be interesting to generate only a fraction of it. Hence, a good algorithm for this purpose should guarantee that it will find as many solutions as we need in a reasonable amount of time. In this case, polynomial incremental time algorithms are more suitable: an algorithm is in polynomial incremental time if the time needed to enumerate the first k solutions is polynomial in k and in the size of the input. Such algorithms naturally appear when the enumeration task is of the following form: given a set of elements and a polynomial time function acting on tuples of elements, produce the closure of the set by the function.

One can generate such closure by iteratively applying the function until no new elements are found. As the set grows bigger, finding new elements becomes harder. For instance, the best algorithm to generate all circuits of a matroid uses some closure property of the circuits [START_REF] Khachiyan | On the complexity of some enumeration problems for matroids[END_REF] and is thus in polynomial incremental time. The fundamental problem of generating the minimal transversals of a hypergraph can also be solved in subexponential incremental time [START_REF] Michael | On the complexity of dualization of monotone disjunctive normal forms[END_REF] and some of its restrictions in polynomial incremental time [START_REF] Eiter | New results on monotone dualization and generating hypergraph transversals[END_REF].

Polynomial incremental time algorithms are not always satisfactory as the delay between the last solutions may be exponentially large. In some cases, the user may be more interested in having a regular stream of solutions. The most efficient enumeration algorithms guarantee a delay between consecutive solutions that is bounded by a polynomial in the input. Polynomial delay algorithms produce solutions regularly and generate the set of solutions in time linear in the size of the output, which can still be overall exponential. There exists two main methods giving polynomial delay algorithms, namely the backtrack search and the reverse search [START_REF] Mary | Énumération des Dominants Minimaux d'un graphe[END_REF]. These methods have been used to give polynomial delay algorithms for enumerating the cycles of a graph [START_REF] Read | Bounds on backtrack algorithms for listing cycles, paths, and spanning trees[END_REF], the satisfying assignments of variants of SAT [START_REF] Creignou | On generating all solutions of generalized satisfiability problems[END_REF], the spanning trees and connected induced subgraphs of a graph [START_REF] Avis | Reverse search for enumeration[END_REF] etc. These methods are particularly efficient as they only need a polynomial space, which is required in practice. Another approach used to enumerate elements of a set while using only polynomial space, is to design and use random generators of solutions, a very active area of research [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]. Following Goldberg [START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF], we also give precise connections between the existence of efficient random generators and efficient randomized enumeration algorithms.

Enumeration algorithms have been studied for the last 40 years [START_REF] Read | Bounds on backtrack algorithms for listing cycles, paths, and spanning trees[END_REF] and the notions of incremental polynomial time and polynomial delay already appear in [START_REF] David S Johnson | On generating all maximal independent sets[END_REF]. However, the structural complexity of enumeration has not been investigated much, one reason being that it seems harder to formalize than decision or counting complexity. Recent works gives a framework for studying the parametrized complexity of enumeration problems [START_REF] Creignou | Paradigms for parameterized enumeration[END_REF] and an analogue of the polynomial hierarchy for the incremental time has been introduced [START_REF] Creignou | On the complexity of hard enumeration problems[END_REF]. The complexity of enumeration when the order of the output is fixed has also been studied, for instance in [START_REF] Creignou | Enumerating all solutions of a boolean CSP by non-decreasing weight[END_REF]. However, from the point of view of structural complexity, it makes enumeration complexity artificial and it mainly boils down to decision complexity as explained in Section 2.4 of [START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF].

The main difficulty in the study of structural complexity of enumeration is that complete problems are known only for EnumP, the equivalent of NP in enumeration, but not for the other natural classes. In this paper, we therefore focus on understanding and separating these classes by using classical hypotheses in complexity theory. Such hypotheses are needed since we ask the generated solutions to be checkable in polynomial time, a reasonable assumption which makes separation of classes much harder. The aim of this paper is twofold. First, we would like it to be usable as a short survey giving the definition of the main enumeration complexity classes with context and open problems as well as folklore results which were scattered over several unpublished works and theses or only implicitly stated in a proof [START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF][START_REF] Schmidt | Complexity and enumeration[END_REF][START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF][START_REF] Bagan | Algorithms and complexity of enumeration problems for the evaluation of logical queries[END_REF][START_REF] Brault-Baron | De la pertinence de l'énumération: complexité en logiques propositionnelle et du premier ordre[END_REF][START_REF] Mary | Énumération des Dominants Minimaux d'un graphe[END_REF]. Second, we prove several new results which connect enumeration complexity to other fields such as fined grained complexity (Exponential Time Hypothesis), total search functions (TFNP) or the count-distinct problem (HyperLogLog).

This article is organized as follows: Sec. 2 is dedicated to the definition of the complexity classes either with polynomial time checkable solutions or not. We use classical complexity hypotheses to prove separation between most classes and provide an equivalence between the separation of incremental and output polynomial time and TFNP = F P . In Sec. 3, we recall how we can simulate algorithms in linear incremental time with polynomial delay algorithms if we allow an exponential space. We also prove that a linear incremental time algorithm which is sufficiently regular can be turned into a polynomial delay and polynomial space algorithm, paving the way for a proof that the two classes are equal. In Sec. 4, we prove new separation results by using the Exponential Time Hypothesis (ETH). More precisely, we exhibit a strict natural hierarchy inside classes of problems having incremental polynomial time algorithms which implies a separation between polynomial delay and incremental polynomial time, the last classes not yet separated. This separation is the first in enumeration complexity to rely on ETH and we believe it can lead to new conditional lower bounds on natural enumeration problems. Finally, in Sec. 5, we consider enumeration problems whose solutions can be given by a polynomial time uniform random generator. We improve a result of [START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF] which shows how to turn a uniform random generator into a randomized polynomial delay algorithm with exponential space. We also show how to get rid of the exponential space if we are willing to allow repetitions by using algorithms to approximate the size of a dynamic set [START_REF] Daniel M Kane | An optimal algorithm for the distinct elements problem[END_REF].

Complexity Classes

Let Σ be a finite alphabet and Σ * be the set of finite words built on Σ. We assume that our alphabet is {0, 1, }. We denote by |x| the size of a word x ∈ Σ * and by |S| the cardinal of a set S. We recall here the definition of an enumeration problem: Definition 1 (Enumeration Problem). Let A ⊆ Σ * ×Σ * be a binary predicate, we write A(x) for the set of y such that A(x, y) holds. The enumeration problem Π A is the function which associates A(x) to x.

From now on, we only consider predicates A such that A(x) is finite for all x. This assumption could be lifted and the definitions on the complexity of enumeration adapted to the infinite case. We chose not to do so to lighten the presentation and because infinite sets of solutions imply some artificial properties when studying the complexity of enumeration. However, there are interesting infinite enumeration problems such as listing all primes or all words of a context-free language [START_REF] Costa Florêncio | Naive infinite enumeration of contextfree languages in incremental polynomial time[END_REF].

The computational model is the random access machine model (RAM) with addition, subtraction and multiplication as its basic arithmetic operations. We have additional output registers, and when a special output instruction is executed, the content of the output registers is produced. A RAM machine solves Π A if, on every input x ∈ Σ * , it produces a sequence y 1 , . . . , y n such that A(x) = {y 1 , . . . , y n } and for all i = j, y i = y j .

To simplify the definitions of complexity classes, we ask the RAM machine to stop immediately after the last output instruction is executed. The cost of every instruction is assumed to be in O(1) except the arithmetic instructions which are of cost linear in the size of their inputs. The space used by the machine at a given step is the sum of the number of bits required to store the integers in its registers.

We denote by T (M, x, i) the sum of the costs of the instructions executed before the i th output instruction. Usually the machine M will be clear from the context and we will write T (x, i) instead of T (M, x, i).

The class EnumP. We can naturally define complexity classes of enumeration problems by restricting the predicate A(x, y) used to define enumeration problems. Definition 2. Let C be a set of binary predicates, Enum • C is the set of problems Π A such that A ∈ C.

As we have explained, we restrict to the enumeration of finite sets: we let F be the set of all A such that, for all x, A(x) is finite and we will often consider Enum • F as the most general class of enumeration problems.

We are mostly interested in the class of problems which are the enumeration of the solutions of an NP problem. Let PtPb be the set of predicates A such that A(x, y) is decidable in Polynomial time and is Polynomially balanced, that is, the elements of A(x) are of size polynomial in |x|. We will denote the class Enum • PtPb by EnumP for resemblance with NP as it is done in [START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF].

The class EnumP has complete problems for the parsimonious reduction borrowed from counting complexity. Definition 3 (Parsimonious Reduction). Let Π A and Π B be two enumeration problems. A parsimonious reduction from Π A to Π B is a pair of polynomial time computable functions f, g such that for all x, g(x) is a bijection between A(x) and B(f (x)).

An EnumP-complete problem is defined as a problem in EnumP to which any problem in EnumP reduces. The problem Π SAT , the task of listing all solutions of a 3-CNF formula is EnumP-complete, since the reduction used in the proof that SAT is NP-complete [START_REF] Stephen | The complexity of theorem-proving procedures[END_REF] is parsimonious. The parsimonious reduction is enough to obtain EnumP-complete problem, but is usually too strong to make some natural candidates complete problems. For instance if we consider the predicate SAT 0(φ, x) which is true if and only if x is a satisfying assignment of the propositional formula φ or x is the all zero assignment, then SAT 0(φ) is never empty and therefore many problems of EnumP cannot be reduced to Π SAT 0 by parsimonious reduction. Many other reductions have been considered [START_REF] Mary | Énumération des Dominants Minimaux d'un graphe[END_REF], inspired by the many one reduction, the Turing reduction or reductions for counting problems [START_REF] Durand | Subtractive reductions and complete problems for counting complexity classes[END_REF]. However, no complete problems are known for the complexity classes we are going to introduce with respect to any of these reductions. This emphases the need to prove separations between enumeration complexity classes since we cannot rely on reductions to understand the hardness of a problem with regard to a complexity class.

The class OutputP. To measure the complexity of an enumeration problem, we consider the total time taken to compute all solutions. Since the number of solutions can be exponential with regard to the input, it is more relevant to give the total time as a function of the size of the input and of the the output. In particular, we would like it to be polynomial in the number of solutions; algorithms with this complexity are said to be in output polynomial time or sometimes in polynomial total time. We define two corresponding classes, one when the problem is in EnumP and one when it is not restricted.

Definition 4 (Output polynomial time).

A problem Π A ∈ EnumP (respectively, in Enum • F) is in OutputP (resp., OutputP F ) if there is a polynomial p(x, y) and a machine M which solves Π A and such that for all x, T (x, |A(x)|) < p(|x|, |A(x)|).

For instance, if we see a polynomial as a set of monomials, then classical algorithms for interpolating multivariate polynomials from their values are output polynomial [START_REF] Zippel | Interpolating polynomials from their values[END_REF] as they produce the polynomial in a time proportional to the number of its monomials. Proof. Assume OutputP = EnumP, thus Π SAT is in OutputP. Then on an instance x, it can be solved in time bounded by p(|x|)q(|SAT (x)|) where p and q are two polynomials. Let c be the constant term of q, if we run the enumeration algorithm for Π SAT and it does not stop before a time cp(|x|), we know there must be a least an element in SAT (x). If it stops before a time cp(|x|), it produces the set SAT (x) therefore we can decide the problem SAT in polynomial time.

Assume now that P = NP. The problem SAT is autoreducible, that is given a formula φ and a partial assignment of its variables a, we can decide whether a can be extended to a satisfying assignment by deciding SAT on another instance. Therefore we can decide in polynomial time if there is an extension to a partial assignment and by using the classical backtrack search or flashlight method (see for instance [START_REF] Mary | Efficient enumeration of solutions produced by closure operations[END_REF]) we obtain an OutputP algorithm for Π SAT , which by completeness of Π SAT for EnumP yields EnumP = OutputP.

The classes EnumP and OutputP may be seen as analog of NP and P for the enumeration. Usually an enumeration problem is considered to be tractable if it is in OutputP, especially if its complexity is linear in the number of solutions. The problems in OutputP are easy to solve when there are few solutions and hard otherwise. We now introduce complexity classes inside OutputP to capture the problems which could be considered as classes of tractable problems even when the number of solutions is high.

The class IncP. From now on, a polynomial time precomputation step is always allowed before the start of the enumeration. It makes the classes of complexity more meaningful, especially their fine grained version. It is usually used in practice to set up useful datastructures or to preprocess the instance.

Given an enumeration problem A, we say that a machine M enumerates A in incremental time f (m)g(n) if on every input x, M enumerates m elements of A(x) in time f (m)g(|x|) for every m ≤ |A(x)|.

Definition 6 (Incremental polynomial time). A problem Π

A ∈ EnumP (re- spectively, in Enum • F) is in IncP a (resp. IncP F a )
if there is a machine M which solves it in incremental time cm a n b for b and c constants. Moreover, we define IncP = a≥1 IncP a and IncP F = a≥1 IncP F a . Let A be a binary predicate, AnotherSol A is the search problem defined as given x and a set S, find y ∈ A(x) \ S or answer that S ⊇ A(x) (see: [START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF][START_REF] Creignou | On the complexity of hard enumeration problems[END_REF]). The problems in IncP are the ones with a polynomial search problem:

Proposition 7 (Proposition 1 of [32]). Let A be a predicate such that Π A ∈ EnumP. AnotherSol A is in FP if and only if Π A is in IncP.
Proof. First assume that AnotherSol A is in FP. Given x, we can enumerate A(x) using the following algorithm: we start with S = ∅ and iteratively add solutions to S by running AnotherSol A (x, S) until no new solution is found, that is, until S = A(x). The delay between the discovery of two new solutions is polynomial in |S| and |x| since AnotherSol A is in FP. Thus, Π A is in IncP. Now assume that Π A is in IncP. That is, we have an algorithm M that given x, output k different elements of A(x) in time c|x| a k b for a, b, c constants. Given x and S, we solve AnotherSol A (x, S) in polynomial time as follows: we simulate M for c|x| a |(1 + |S|) b steps. If the algorithm stops before that, then we have completely generated A(x). It is then sufficient to look for y ∈ A(x) \ S or, if no such y exists, output that S ⊇ A(x). If the algorithm has not stopped yet, then we know that we have found |S| + 1 elements of A(x). At least one of them is not in S and we return it.

The class IncP is usually defined as the class of problems solvable by an algorithm with a delay polynomial in the number of already generated solutions and in the size of the input. This alternative definition is motivated by saturation algorithms, which generates solutions by applying some polynomial time rules to enrich the set of solutions until saturation. There are many saturation algorithms, for instance to enumerate circuits of matroids [START_REF] Khachiyan | On the complexity of some enumeration problems for matroids[END_REF] or to compute closure by set operations [START_REF] Mary | Efficient enumeration of solutions produced by closure operations[END_REF].

Definition 8 (Usual definition of incremental time.). A problem Π

A ∈ EnumP (respectively in Enum • F) is in UsualIncP a if
there is a machine M which solves it such that for all x and for all 0 < t ≤ |A(x)|, |T (x, t) -T (x, t -1)| < ct a |x| b for b and c constants. Moreover, we define UsualIncP = a≥1 UsualIncP a .

With our definition, we capture the fact that investing more time guarantees more solutions to be output, which is a bit more general at first sight than bounding the delay because the time between two solutions is not necessarily regular. We will see in Sec. 3 that both definitions are actually equivalent but the price for regularity is to use exponential space.

We now relate the complexity of IncP to the complexity of the class TFNP introduced in [START_REF] Megiddo | On total functions, existence theorems and computational complexity[END_REF]. A problem in TFNP is a polynomially balanced polynomial time predicate A such that for all x, A(x) is not empty. An algorithm solving a problem A of TFNP on input x outputs one element of A(x). The class TFNP can also be seen as the functional version of NP ∩ coNP. Proof. Let A be in TFNP and let q be a polynomial such that if A(x, y) then |y| ≤ q(|x|). We define C(x, y w) the predicate which is true if and only if A(x, y) and |w| ≤ q(|x|). Observe that the set C(x) is never empty by definition of TFNP. Thanks to the padding, there are more than 2 |w| = 2 q(|x|) elements in C(x) for each y such that A(x, y). Therefore the trivial enumeration algorithm testing every solution of the form y w is polynomial in the number of solutions, which proves that Π C is in OutputP.

If IncP = OutputP, we have an incremental algorithm for Π C . In particular, it gives, on any instance x, the first solution y w in polynomial time. This is a polynomial time algorithm to solve the TFNP problem A, thus TFNP = FP. Now assume that TFNP = FP and let Π A be in OutputP. We assume w.l.o.g. that the predicate A is defined over ({0, 1} * ) 2 and we define the relation D((x, S), y) which is true if and only if

• either y ∈ A(x) \ S,
• or y = and S ⊇ A(x).

We show that D is in TFNP. First, observe that the relation D is total by construction. Now, since Π A ∈ OutputP ⊆ EnumP, the y such that A(x, y) holds are of size polynomial in |x| which proves that D is polynomially balanced.

It remains to show that one can decide D((x, S), y) in time polynomial in the size of x, S and y. The algorithm is as follows: if y = , then D((x, S), y) holds if and only if y ∈ A(x)\S. Testing whether y / ∈ S can obviously be done in polynomial time in the size of y and S. Now, recall that Π A ∈ EnumP, thus we can also test whether y ∈ A(x) holds in polynomial time. Now assume that y = . Then D((x, S), ) holds if and only if S ⊇ A(x). By assumption, A ∈ OutputP, thus we have an algorithm that given x, generates A(x) in time c|x| a |A(x)| b for constants a, b, c. We simulate this algorithm for at most c|x| a |S| b steps. If the algorithm stops before the end of the simulation, then we have successfully generated A(x) and it remains to check if S ⊇ A(x) which can be done in polynomial time. Now, if the algorithm has not stopped after having simulating c|x| a |S| b steps, it means that |A(x)| > |S|. Thus, S A(x) and we know that D((x, S), ) does not hold.

We have proved that D ∈ TFNP. Since we have assumed that TFNP = FP we can, given (x, S), find y such that y ∈ A(x) \ S or decide there is none. In other words the problem AnotherSol A is in FP and it implies that Π A ∈ IncP by Proposition 7. This is yet a new link between complexity of enumeration and another domain of computer science, namely the complexity of total search problem. It is interesting since enumeration complexity is often understood only by relating it to decision complexity, as in Prop. 5. Moreover recent progress on the understanding of TFNP may help us to understand the class IncP. For instance, it has been proven that reasonable assumptions such as the existence of one way functions are enough to imply FP = TFNP [START_REF] Hubácek | The journey from np to tfnp hardness[END_REF] and thus IncP = OutputP.

Observe that without the requirement to be in EnumP, incremental polynomial time and output polynomial time are separated unconditionally.

Proposition 10. IncP F = OutputP F .
Proof. Choose any EXP-complete decision problem L and let A be the predicate such that A(x, y) holds if and only if

x = 0 i if x ∈ L or 1 i if x / ∈ L with 0 ≤ i < 2 |x|
. Therefore Π A is easy to solve in linear total time, but since EXP = P we cannot produce the first solution in polynomial time and thus Π A is not in incremental polynomial time.

The class DelayP. We now define the polynomial delay which by definition is a subclass of IncP 1 . In Sec. 3 we study its relationship with IncP 1 , while in Sec.4 we prove its separation from IncP.

Definition 11 (Polynomial delay). A problem Π

A ∈ EnumP (respectively in Enum • F) is in DelayP (resp. in DelayP F ) if
there is a machine M which solves it such that for all x and for all 0 < t ≤ |A(x)|, |T (x, t)-T (x, t-1)| < C|x| c for C and c constants.

Observe that, by definition, DelayP = UsualIncP 0 .

Space and regularity of enumeration algorithms

The main difference between IncP 1 and DelayP is the regularity of the delay between two solutions. In several algorithms, for instance to generate maximal cliques [START_REF] David S Johnson | On generating all maximal independent sets[END_REF], an exponential queue is used to store results, which are then output regularly to guarantee a polynomial delay. This is in fact a general method which can be used to prove that IncP 1 = DelayP and, more generally, IncP a+1 = UsualIncP a . Proposition 12. For every a ∈ N, IncP a+1 = UsualIncP a .

Proof. Let Π A ∈ UsualIncP a , then there is an algorithm I and constants C and c such that I on input x produces k solutions in time bounded by

k i=0 C|x| c i a = C|x| c ( k i=0 i a ) ≤ C|x| c (k + 1)k a ≤ 2C|x| c k a+1 . Thus Π A ∈ IncP a+1 .
Now let Π A ∈ IncP a+1 , then there is an algorithm I which on an instance of size n, produces k solutions in time bounded by k a+1 p(n) where p is a polynomial.

We construct an algorithm I which solves Π A with delay O(p(n)q(k) + s) between the k th and the (k + 1) th output solution, where s is a bound on the size of a solution and q(k) = (k + 1) a+1 -k a+1 . The algorithm I simulates I together with a counter c that is incremented at each step of I and a counter k which is initially set to 1. Each time I outputs a solution, we append it to a queue instead. Each time c reaches p(n)k a+1 , the first solution of is output, removed and k is incremented.

It is easy to see that during the execution of I , k -1 always contains the number of solutions that have been output by I so far. Thus when c reaches p(n)k a+1 , I is guaranteed to have found k solutions and I has only output k -1 of them, thus is not empty or it is the end of the execution of I. Moreover, the time elapsed between I outputs the k th and the (k + 1) th solutions is the time needed to update the counters, plus the time needed to write a solution which is linear in s plus (k+1) a+1 p(n)-k a+1 p(n) = q(k)p(n). Thus, the delay of I between the k th and the (k + 1) th output solution is

O(p(n)q(k) + s). Since Π A ∈ IncP a+1 , we also have Π A ∈ EnumP, thus s is polynomial in n. Moreover q(k) = O(k a ). That is, Π A ∈ UsualIncP a .
By choosing a = 0 in Proposition 12, we directly get the interesting following result: Corollary 13. IncP 1 = DelayP and IncP = UsualIncP.

An inconvenience of Proposition 12 is that the method used to go from our notion of incremental polynomial time to the usual notion of incremental time may blow up the memory. In practice, incremental delay is relevant if we also use only polynomial space. This naturally raises the question of understanding the relationship between IncP a+1 and UsualIncP a when the space is required to be polynomial in the size of the input.

As the more relevant classes in practice are DelayP and IncP 1 , we are concretely interested in the following question: does every problem in IncP 1 with polynomial space also have an algorithm in DelayP with polynomial space? Unfortunately, no classical assumptions in complexity theory seem to help for separating these classes nor were we able to prove the equality of both classes. The rest of this section is dedicated to particular IncP 1 algorithms where the enumeration is sufficiently regular to be transformed into DelayP algorithm without blowing up the memory.

An algorithm I is incremental linear if there exists a polynomial h such that on any instance of size n, it produces k solutions in time bounded by kh(n). We call h the average delay of I. By definition, a problem Π A ∈ EnumP is in IncP 1 if and only if there exists an incremental linear algorithm solving Π A .

Let I be an incremental linear algorithm. Recall that T (I, x, i) is number of steps made by I before outputting the i th solution. To make notations lighter, we will write T (i) since x and I will be clear from the context. Consider a run of I on the instance x, we will call m i an encoding of i, the memory of I and its state at the time it outputs the i th solution. We say that the index i is a p-gap of I if T (i + 1) -T (i) > p(|x|). If I has no p gaps for some polynomial p, it has polynomial delay p. We now show that when the number of large gaps is small, we can turn an incremental linear algorithm into a polynomial delay one, by computing shortcuts in advance. Proposition 14. Let Π A ∈ IncP 1 and I be an incremental linear algorithm for Π A using polynomial space. Assume there are two polynomials p and q such that for all instances x of size n, there are at most q(n) p-gaps in the run of I, then Π A ∈ DelayP with polynomial space.

Proof. Since I is incremental linear it has a polynomial average delay that we denote by h. We run in parallel two copies of the algorithm I that we call I 1 and I 2 . When I 1 simulates one computation step of I, I 2 simulates 2h(n) computation steps of I.

Moreover I 2 has a counter that is incremented each time a step of I is simulated and reset each time a solution is found. Using this counter, I 2 can detect p-gaps: when I 2 is about to output solution i + 1, it checks if the value of the counter is bigger than p(n). If it is the case, then I 2 has detected a p-gap and it stores the pair (i, m i+1 ) where m i+1 is the description of the machine I just before it outputs the (i + 1) th solution. Since there are at most q(n) p-gaps and because I uses polynomial space, the memory used by I 2 is polynomial.

When I 1 outputs a solution of index i, it checks if I 2 has stored a tuple (i, m i+1 ). If so, then we know that there is a p-gap there and I 1 jumps directly to the configuration m i+1 .

Observe that even if I 1 jumps at solution i, I 2 will still simulate 2h(n) steps of I before I 1 simulates the next step of I. Thus, when I 1 discover the i th solution, I 2 has already simulated at least 2h(n)i steps of I. Since I is incremental linear, T (i + 1) ≤ (i + 1)h(n) ≤ 2ih(n). In other words, when I 1 discover the i th solution, I 2 has already discovered the (i + 1) th solution and detected a possible p-gap for I 1 to jump.

In that way, I 1 will always generate solutions with delay O(p(n)h(n))1 because I 1 has no p-gaps by construction, and each of its computation steps involves h(n) computation steps of I 2 .

We can prove something more general, by requiring the existence of a large interval of solutions without p-gaps rather than bounding the number of gaps. It captures more cases, for instance an algorithm which outputs an exponential number of solutions at the beginning without gaps and then has a superpolynomial number of gaps. The idea is to compensate for the gaps by using the dense parts of the enumeration. Proposition 15. Let Π A ∈ IncP 1 and I be an incremental linear algorithm for Π A using polynomial space. Assume there are two polynomials p and q such that for all x of size n, and for all k ≤ |A(x)| there exists a < b ≤ k such that b -a > k q(n) and there are no p-gaps between the a th and the b th solution. Then Π A ∈ DelayP with polynomial space.

Proof. We let h be the average delay of I. We fix x of length n and describe a process that enumerates A with delay at most 2q(n)h(n) • (q(n)h(n) + p(n)) and polynomial space on input x. Our algorithm runs two processes in parallel: En, the enumerator and Ex, the explorer. Both processes simulate I on input x but at a different speed that we will fix later in the proof. En is the only one outputting solutions. We call a solution fresh if it has not yet been enumerated by En.

Ex simulates I and discovers the boundaries of the largest interval without p-gaps containing only fresh solutions that we call the stock. More precisely, it stores two machine states: m a and m b where a and b correspond to indices of fresh solutions such that there are no p-gaps between a and b and it is the largest such interval. Intuitively, the stock contains the fresh solutions that will make up for p-gaps in the enumeration of I.

En can work in two different modes. If En is in simple mode, then it only simulates I on input x and outputs a solution whenever I outputs one and counts the number of steps between two solutions. When it detects a p-gap, En switches to filling mode. In filling mode, En starts by copying m a into a new variable s and m b into a new variable t. It then runs two simulations of I: the first one is the continuation of the simulation that was done in simple mode. The second one, which we call the filling simulation is a simulation of I starting in state m a . En simulates h(n)q(n) steps of the first enumeration and then as many steps as necessary to find the next solution of the filling simulation. Since the stock does not contain p-gaps by definition, we know that En outputs solutions with delay at most h(n)q(n) + p(n). To avoid enumerating the same solution twice, whenever the first simulation reaches the state stored in s, we stop the first simulation and En switches again in simple mode using the filling simulation as starting point.

We claim that the first simulation will always reach state s before the filling simulation reach the end of the stock. Indeed, assume that the filling simulation has reached the end of the stock and outputs the b th solution. By definition, the stock is the largest interval without p-gaps before this solution and it is of size at least b/q(n) by assumption. Thus, the first simulation has simulated at least (b/q(n))h(n)q(n) = b • h(n) steps of I in parallel. Thus, by definition of h, the b first solutions have been found by the first simulation. It must have reached state s before the filling simulation reaches the end of the interval.

Using this strategy, it is readily verified that if En has always a sufficiently large stock at hand, it enumerates A(x) entirely with delay at most h(n)q(n)+ p(n).

We now choose the speed of Ex in order to guarantee that the stock is always sufficiently large: each time En simulates one step of I, Ex simulates 2h(n)q(n) steps of I.

There is only one situation that could go wrong: the enumerator can reach state m b , which is followed by a p-gap while the explorer has not found a new stock yet. We claim that having chosen the speed as we did, we are guaranteed that it never happens. Indeed, if En reaches m b , then it has already output b solutions. Thus, Ex has already simulated at least b•2h(n)q(n) steps of I. By definition of h, Ex has already found 2b • q(n) solutions and then, it has found an interval without p-gaps of size (2b

• q(n))/q(n) = 2b
which is necessarily ahead of the simulation of En.

The property of the last paragraph is only true if the simulation of I by Ex has not stopped before b • 2h(n)q(n) steps. To deal with this case, as soon as Ex stopped, En enters in filling mode if it was not in this mode and does a third simulation in parallel of I beginning at state m b . This takes care of the solutions after the last stock.

Note that in both proofs the polynomial delay we obtain is worse than the average delay of the incremental algorithm but the total time is the same. Also we do not use all properties of an algorithm in IncP 1 but only the fact that the predicate is polynomially balanced. All known algorithms which are both incremental and in polynomial space are in fact polynomial delay algorithms with a bounded number of repetitions and a polynomial time algorithm to decide whether it is the first time a solution is produced [START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF]. It seems that if we can turn such an algorithm to one in polynomial delay, we would have solved the general problem.

Open problem 1. Prove or disprove that IncP 1 with polynomial space is equal to DelayP with polynomial space.

Here we tried to improve the regularity of an algorithm without losing too much memory. The opposite question is also natural: is it possible to trade regularity and total time for space in enumeration. In particular can we improve the memory used by an enumeration algorithm if we are relaxing the constraints on the delay.

Open problem 2. Can we turn a polynomial delay algorithm using an exponential space memory into an output polynomial or even an incremental polynomial algorithm with polynomial memory ?

Strict hierarchy in incremental time problems

We prove strict hierarchies for IncP F a unconditionally and for IncP a modulo the Exponential Time Hypothesis (ETH). Since DelayP ⊆ IncP 1 it implies that DelayP = IncP modulo ETH.

Proposition 16. IncP F a IncP F b when 1 ≤ a < b. Proof.
By the time hierarchy theorem [START_REF] Hartmanis | On the computational complexity of algorithms[END_REF], there exists a language L which can be decided in time O(2 nb ) but not in time O(2 na ). Let n = |x|. We build a predicate A(x, y) which is true if and only if either y is a positive integer written in binary with y < 2 n or y = 0 when x / ∈ L or y = 1 when x ∈ L. We have an algorithm to solve Π A : first enumerate the 2 n trivial solutions then run the O(2 nb ) algorithm which solves A to compute the last solution. This algorithm is in IncP F b , since finding the 2 n first solutions can be done in IncP 1 and the last one can be found in time O((2 n ) b ). Assume there is an IncP F a algorithm to solve Π A with a precomputation step bounded by the polynomial p(n). By running this enumeration algorithm for a time O(p(n) + 2 na ) = O(2 na ) we are guaranteed to find all solutions. Therefore one finds either the solution 0 or 1 in time O(2 na ) which is a contradiction therefore Π A / ∈ IncP F a . This proof can easily be adapted to prove an unconditional hierarchy inside OutputP F and DelayP F . In the case of DelayP F , one must use a padding and a complexity for L of n log(n) to dominate the precomputation step while satisfying the hypothesis of the time hierarchy theorem.

To prove the existence of a strict hierarchy in IncP, we need to assume some complexity hypothesis since P = NP implies IncP = IncP 1 by the same argument as in the proof of Prop. 5. Moreover, the hypothesis must be strong enough to replace the time hierarchy argument.

The Exponential Time Hypothesis states that there exists > 0 such that there is no algorithm for 3-SAT in time Õ(2 n ) where n is the number of variables of the formula and Õ means that we have a factor of n O (1) . The Strong Exponential Time Hypothesis (SETH) states that for every < 1, there is no algorithm solving SAT in time Õ(2 n ).

We show that if ETH holds, then IncP a IncP b for all a < b. For t ≤ 1, let R t be the following predicate: given a CNF φ with n variables, R t (φ) contains:

• the integers from 1 to 2 nt -1

• the satisfying assignments of φ duplicated 2 n times each, that is

SAT (φ)× [2 n ].
We let Pad t be the enumeration problem associated to R t , that is Pad t = Π Rt . The intuition behind Pad t is the following. Imagine that t = b -1 for Observe that by Proposition 12 and Theorem 20, we also have that if ETH holds, then we also have a strict hierarchy inside UsualIncP.

In the previous proofs, we did not really use SAT. We needed an NP problem, with a set of easy to enumerate potential solutions of size 2 n that cannot be solved in time 2 o(n) . For instance we could use CIRCUIT-SAT which is the problem of finding a satisfying assignment to a Boolean circuit. We can thus prove our result by assuming a weaker version of ETH as it is done in [START_REF] Abboud | Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made[END_REF]. It would be nice to further weaken the hypothesis, but it seems hard to rely only on a classical complexity hypothesis such as P = NP. The other way we could improve this result, is to prove a lower bound for a natural enumeration problem instead of Pad t .

Open problem 3. Prove that enumerating the minimal transversals of a hypergraph cannot be done in IncP 1 if ETH holds.

It is also natural to try to obtain the same hierarchy for DelayP. However, the difference in total time between two algorithms with different polynomial delays is very small and the proof for the separation of the incremental hierarchy does not seem to carry on.

Open problem 4. Prove there is a strict hierarchy inside DelayP assuming SETH or even stronger hypotheses.

From Uniform Generator to efficient randomized enumeration

In this section, we explore the relationship between efficient enumeration and random generation of combinatorial structures or sampling. The link between sampling and counting combinatorial structures has already been studied. For instance, Markov Chain Monte Carlo algorithms can be used to compute an approximate number of objects [START_REF] Jerrum | Counting, sampling and integrating: algorithms and complexity[END_REF] or in the other direction, generating functions encoding the number of objects of each size can be used to obtain Boltzman samplers [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF].

In her thesis [START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF] (Section 2.1.2), Leslie Goldberg proved several results relating the existence of a good sampling algorithm for a set S with the existence of an efficient algorithm to enumerate S. In this section, we review these results and improve the runtime of the underlying algorithms. Moreover, we show that if we allow repetitions during the enumeration, we can design algorithms using only polynomial space. This complements a result by Goldberg (Theorem 3, p.33 in [START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF]) showing a space-time trade-off if we do not relax the notion of enumeration.

Definition 21. Let Π A ∈ EnumP. A polytime uniform generator for A is a randomized RAM machine M which outputs an element y of A(x) in time polynomial in |x| such that the probability over every possible run of M on input x that M outputs y is |A(x)| -1 .

We now define a randomized version of IncP, which has first been introduced in [START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF][START_REF] Strozecki | On enumerating monomials and other combinatorial structures by polynomial interpolation[END_REF] to capture random polynomial interpolation algorithms. Proof. Algorithm 1 shows how to use a generator for A to enumerate its solutions in randomized IncP 1 . The idea is the most simple: we keep drawing elements of A(x) uniformly by using the generator. If the drawn element has not already been enumerated, then we output it and remember it in a set E. We keep track of the total number of draws in the variable r. If this variable reaches a value that is much higher than the number of distinct elements found at this point, we stop the algorithm. We claim that Algorithm 1 is in randomized IncP 1 , the analysis is similar to the classical coupon collector theorem [START_REF] Erdos | On a classical problem of probability theory[END_REF].

Algorithm 1: An algorithm to enumerate Π A in randomized IncP 1 , where every element of A(x) is of size at most p(|x|).

Data: We let p be a polynomial such that for every x ∈ {0, 1} * , the size of elements of A(x) is at most p(|x|). Such a polynomial exists since Π A ∈ EnumP. Observe that all operations can be done in polynomial time in |x| since we can encode E -the set of elements that have already been enumerated -by using a datastructure such as a trie for which adding and searching for an element may be done in time O(p(|x|), the size of the element.

x ∈ {0, 1}, ∈ Q + begin E ← ∅; r ← 0; K ← 2 • p(|x|) -log( /
Moreover, observe that if the algorithm is still running after tK executions of the while loop, then we have |E| ≥ t, thus we have enumerated more than t elements of A(x). Since each loop takes a time polynomial in |x| and K is polynomial in |x| and , we have that if the algorithm still runs after a time t • poly(|x|), then the run is similar to a run in IncP 1 .

Hence, to show that Π A is in randomized IncP 1 , it only remains to prove that the probability that Algorithm 1 stops before having enumerated A(x) completely is smaller than . The main difficulty is to decide when to stop. It cannot be done deterministically since we do not know |A(x)| a priori. Algorithm 1 stops when the total number of draws r is larger than K • |E|, where E is the set of already enumerated elements of A(x). In the rest of the proof, we prove that with K = 2 • p(|x|) -log( /2) , Algorithm 1 stops after having enumerated A(x) completely with probability greater than 1 -.

In the following, we fix x ∈ {0, 1} * and ∈ Q + . We denote by s = |A(x)| the size of A(x). Remember that we have s ≤ 2 p(|x|) . We denote by T the random variable whose value is the number of distinct elements of A(x) that have been enumerated when the algorithm stops. Our goal is to show that P(T < s) ≤ .

We start by showing that P(T ≤ s/2) ≤ /2. Let t ≤ s/2. We bound the probability that T = t. If the algorithm stops after having found t solutions, we know that it has found t solutions in less than 1+(t-1)K draws, otherwise, if the algorithm had found less than t solutions after 1 + (t -1)K draws then the while loop would have finished. After that, it keeps on drawing already enumerated solutions until it has done 1 + tK draws and stops. Thus, it does at least K draws without finding new solutions. Since t ≤ s/2, the probability of drawing a solution that was already found is at most 1/2. Thus for all t ≤ s/2,

P(T = t) ≤ 2 -K ≤ 2 -p(|x|) ( /2) since K = 2 • p(|x|) -log( /2
) . Now, applying the union bound yields: |x|) . Now, we show that P(s/2 < T < s) ≤ /2. Assume that T > s/2. Then, after K • (s/2) draws, the algorithm has not stopped. Thus the probability that s/2 < T < s is smaller than the probability that, after r = K • (s/2) draws, we have not found every element of A(x). Given an element y ∈ A(x), the probability that y is not drawn after r draws is (1 -1/s) r . Thus, the probability that after r = K • (s/2) draws, we have not found every element of A(x) is at most

P(T ≤ s/2) ≤ s/2 t=1 P(T = t) ≤ (s/2)2 -p(|x|) ( /2) ≤ /2 since s ≤ 2 p(
s • (1 -1/s) r ≤ s • 2 -r/s ≤ s • 2 log( /2)-p(|x|) since r = K • (s/2) ≤ /2 • s2 -p(|x|) ≤ /2 since s ≤ 2 p(|x|)
In the end, P(T < s) ≤ P(T ≤ s/2) + P(s/2 < T < s) ≤ . We observe that the running time of Algorithm 1 is actually polynomial in log( -1 ) which is a much better bound than the one of Definition 22 since log( -1 ) is polynomial in the size of the encoding of for < 1.

Applying the same technique as Prop. 12, we can turn Algorithm 1 into a randomized DelayP algorithm by amortizing the generation of solutions.

Corollary 24. If Π A ∈ EnumP has a polytime uniform generator, then Π A is in randomized DelayP.

In [START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF], Goldberg uses generators that are not necessarily uniform and may be biased by a factor b. We can easily modify Algorithm 1 to make it work with a biased generator. Polynomial space algorithm. The main default of Algorithm 1 is that it stores all solutions enumerated and therefore needs a space which may be exponential. It seems necessary to encode the subset of already generated solutions and these subsets are in doubly exponential number and thus cannot be encoded in polynomial space. Therefore the enumeration algorithm needs time to rule out a large number of possible subsets of generated solutions. This idea has been made precise by Goldberg (Theorem 3, p.33 [START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF]): the product of the delay and the space is lower bounded by the number of solutions to output up to a polynomial factor. On the other hand it is easy to build an enumeration algorithm with such space and delay, by generating solutions by blocks in lexicographic order (Theorem 5, p.42 [START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF]). The proof of the lower bound uses the fact that the enumeration algorithm can only output solutions which are given by calls to the generator. A set of possible initial sequences of output elements in the enumeration is built so that its cardinality is bounded by an exponential in the space used and that the enumeration produces one of these sequences with high probability. Then, if the delay is too small, with high probability the calls to the generator have not produced any of those special sequences which ends the proof.

However, if we allow unbounded repetitions of solutions in the enumeration algorithm we can devise an incremental polynomial algorithm with polynomial space. The main difficulty is again to decide when to stop so that no solution is forgotten with high probability. The method used in Algorithm 1 does not work in this case since we cannot maintain the number of distinct solutions that have been output so far. However, there exist data structures which allow to approximate the cardinal of a dynamic set using only a logarithmic number of bits in the size of the set [START_REF] Flajolet | Probabilistic counting algorithms for data base applications[END_REF][START_REF] Daniel M Kane | An optimal algorithm for the distinct elements problem[END_REF]. The idea is to apply a hash function to each element seen and to remember an aggregated information on the bits of the hashed elements. Algorithm 2 shows how we can exploit such datastructures to design a randomized incremental algorithm from a uniform generator. Unlike Algorithm 1, Algorithm 2 cannot be turned into a polynomial delay algorithm since it would require exponential space and our improvement would then be useless. Proof. The procedure update in Algorithm 2 maintains a data structure which allows estimate to output an approximation of |E|. If we use the results of [START_REF] Daniel M Kane | An optimal algorithm for the distinct elements problem[END_REF], we can get a 2-approximation of |E| during all the algorithm with probability 1 -/2. The data structure uses a space log(|E|) log( -1 ). The process update(E, e) does O(log( -1 )) arithmetic operations and estimate does O(1) arithmetic operations. The arithmetic operations are over solutions seen as integers which are of size polynomial in n. The analysis of the delay is the same as before, but to the cost of generating a solution, we add the cost of computing update(E, e) and estimate which are also polynomial in n.

The analysis of the correctness of the algorithm is the same, except that now v is a 2-approximation of |E| with probability 1-2 . We have adapted the value of K such that with probability /2 the algorithm will not stop before generating all solutions even if |E| is approximated by |E|/2. Therefore the probability to wrongly evaluate |E| plus the probability that the algorithm stops too early is less than . The method we just described here can be relevant, when we have an enumeration algorithm using the supergraph method: a connected graph whose vertices are all the solutions is defined in such a way that the edges incident to a vertex can be enumerated with polynomial delay. The enumeration algorithm does a traversal of this graph which requires to store all generated solutions to navigate the graph. The memory used can thus be exponential. On the other hand doing a random walk over the graph of solutions often yields a polynomial time uniform generator. If it is the case using Algorithm 2 we get a randomized polynomial delay algorithm using polynomial space only.

The more classical way to avoid exponential memory is Lawler's method [START_REF] Lawler | Generating all maximal independent sets: Np-hardness and polynomial-time algorithms[END_REF] or reverse search, that is defining an implicit spanning tree in the graph which can be navigated with polynomial memory. This method is not always relevant since it is based on solving a search problem which may be NP-hard. One could also traverse the graph of solutions using only a logarithmic space in the numbers of solutions using a universal sequence [START_REF] Reingold | Undirected connectivity in log-space[END_REF] but this method gives no guarantee on the delay and has a huge slowdown in practice.

Proposition 5 .

 5 OutputP = EnumP if and only if P = NP.

Proposition 9 .

 9 If TFNP = FP if and only if IncP = OutputP.

Theorem 20 .

 20 If ETH holds, then IncP a IncP b for all a < b. Proof. If there exists a < b such that IncP a = IncP b , then by Lemma 19, for all i, Pad a i b i+1 is in IncP a . Thus by Lemma 18, we have an Õ(2 d i n ) algorithm for SAT and then for 3-SAT in particular, where d i = a b i . Since lim i→∞ d i = 0, this contradicts ETH.

Definition 22 .

 22 A problem Π A is in randomized IncP k if Π A ∈ EnumP and there exists constants a, b, c ∈ N and a randomized RAM machine M such that for every x ∈ {0, 1} * and ∈ Q + , the probability that M , on input x and , enumerates A(x) in incremental time cm k n a -b is greater than 1 -.Definition 22 can be understood as follows, on input x ∈ {0, 1} * and ∈ Q + , the probability of the following fact is at least 1 -: for every t ≤ |A(x)|, M has enumerated t distinct elements of A(x) after ct k n a -b steps and stops in time less than |A(x)| k n a -b . Theorem 23. If Π A ∈ EnumP has a polytime uniform generator, then Π A is in randomized IncP 1 .

Definition 25 .

 25 Let Π A ∈ EnumP and b a polynomial. A polytime b-biased generator for A is a randomized RAM machine M which outputs an element y of A(x) in time polynomial in |x| such that the probability over every possible run of M on input x that M outputs y is at least|A(x)|b(x) -1 . Theorem 26. If Π ∈ EnumP has a polytime b-biased generator, then Π A is in randomized IncP 1 . Proof (sketch). It is sufficient to replace K ← 2 • p(|x|) -log( /2) in Algorithm 1 by K ← 2 • b(|x|) • p(|x|) -log( /2) . The proof follows then exactly the proof of Theorem 23.Theorem 26 is an improved version of Theorem 2, Section 2.1.2 in[START_REF] Leslie | Efficient algorithms for listing combinatorial structures[END_REF]. It is not hard to see that in our algorithm, the average delay between two solutions is O(p(|x|)g(|x|)b(|x|)) where g is the runtime of the generator. The average delay of Goldberg's algorithm is, with our notations, O(p(|x|) 3 g(|x|)b(|x|)).

Algorithm 2 :

 2 An algorithm in randomized IncP 1 with polynomial space such that every element of A(x) is of size at most p(|x|).Data:x ∈ {0, 1}, ∈ Q + begin Initialize E; r ← 0; K ← 4 • p(|x|) -log( /4) ; while r ≤ K • estimate(E) do Draw e ∈ A(x) uniformly and r ← r + 1; Output e and update(E, e); Proposition 27. If Π A ∈ EnumP has a polytime uniform generator, then there is an enumeration algorithm in randomized IncP 1 with repetitions and polynomial space.

The constant hidden in O(. . . ) here comes from the cost of simulations.

Acknowledgment

We are thankful to Arnaud Durand for numerous conversations about enumeration complexity and for having introduced the subject to us. This work was partially supported by the French Agence Nationale de la Recherche, AGGREG project reference ANR-14-CE25-0017-01 and by the ESPRC grant EP/LO20408/1.

some b ∈ N. By adding sufficiently many dummy solutions to the satisfying assignments of a CNF-formula φ, we can first enumerate them quickly and then have sufficient time to bruteforce SAT (φ) in IncP b before outputting the next solution. This shows that Pad b -1 ∈ IncP b . Now, if there exists a < b such that IncP a = IncP b , we would have a way to find a solution of φ in time Õ(2 a b n ) which already violates SETH. To show that we also violate ETH we repeat this trick but we do not bruteforce SAT(φ) anymore. We can do better by using this Õ(2 a b n ) algorithm for SAT and we can gain a bit more on the constant in the exponent. We show that by repeating this trick, we can make the constant as small as we want. We formalize this idea:

Proof. We enumerate the integers from 1 to 2 dn b -1 and then call the algorithm to find a satisfying assignment of φ. We have enough time to run this algorithm since the time allowed before the next answer is Õ 2

). If the formula is not satisfiable, then we stop the enumeration. Otherwise, we enumerate all copies of the discovered solution. We have then enough time to bruteforce the other solutions.

Lemma 18. If Pad t is in IncP a , then there exists an Õ(2 nta ) algorithm for SAT.

Proof. Since Pad t is in IncP a , we have an algorithm for Pad t that outputs m elements of R t (φ) in time O(m a |φ| c ) for a constant c. We can then output 2 nt elements of R t (φ) in time O(2 nta |φ| c ) = Õ(2 nta ). If the enumeration stops before having output 2 nt solutions, then the formula is not satisfiable. Otherwise, we have necessarily enumerated at least one satisfying assignment of φ which gives the algorithm.


Amanda Maria Tadini
email: amandatadini@hotmail.com

Stephane Mounier

Marcondes Débora

Pereira Bastos

Milori

Modeling the quenching of fluorescence from organic matter in Amazonian soils

Keywords: Humic Fractions, Complexation, Mobility, Amazonian Spodosol

Knowledge of the interactions of soil organic matter (SOM) with metal species is important in order to obtain information concerning the fates of the metals in environment, whose reactive functional groups present in SOM can provide high complexation capacity. The aim of this study was to evaluate the interactions involving humic acids (HA) and fulvic acids (FA), extracted from Amazonian soils, with Cu(II) and Al(III) ions, using fluorescence quenching spectroscopy. The obtained results showed that the data for the humic fractions of the Amazonian Spodosols could be fitted with one to one complexation model, which provided the best representation of the changes in fluorescence quenching after addition of Cu(II) or Al(III) ions. It was found that the HA presented fewer complexation sites and lower stability constants, compared to the FA samples. Furthermore, the FA showed selective interaction with the metals, while the HA fraction was less selective and could be associated its homogeneous structure. The results showed that the humic acids required 10 times more carbon in their structures than fulvic acids for complexing a metal atom. This behavior can be associated to the fact that the Fulvic Acid fraction has higher mobility and greater interaction during the profile when compare humic acids. Hence, given the diversity of metals to which the HA has affinity, this soil fraction appears to be mainly responsible for soil fertility, while the FA fraction has higher mobility and greater interaction with water.

Introduction

Determination of the chemical properties of the soil organic matter, as well as its interaction with metallic species, provides important information for understanding the structures of the humic fractions. The humic substances (HS) are composed of aromatic rings and reactive functional groups that are responsible for the high capacity for complexation with metals, highlighting copper and aluminum species [START_REF] Paul | The nature and dynamics of soil organic matter: Plant inputs, microbial transformations, and organic matter stabilization[END_REF].

Quenching analysis is based on decrease of the fluorescence intensity of a sample, usually due to molecular interactions [START_REF] Manciulea | A fluorescence quenching study of the interaction of Suwannee River fulvic acid with iron oxide nanoparticles[END_REF]). These interactions include reactions in the excited state, molecular rearrangements, complex formation in the ground state and collision energy transfer (Esteves da Silva et al. 1998;[START_REF] Mounier | Copper complexing properties of dissolved organic matter: PARAFAC treatment of fluorescence quenching[END_REF]. Quenching analysis of a sample, in the presence of metallic ions, can involve two mechanisms: dynamic quenching and static quenching. Dynamic quenching is a process involving collision, in which the fluorophore and the quenching agent (for example, a metal) come into contact and energy transfer occurs between the molecules in the excited state (collisional process). Static quenching involves an equilibrium complexation process in which fewer (or no) fluorescent complexes of the fluorophore in the ground state are formed [START_REF] Kumke | Fluorescence decay of natural organic matter (NOM) and influence of fractionation, oxidation, and metal ion complexation[END_REF][START_REF] Manciulea | A fluorescence quenching study of the interaction of Suwannee River fulvic acid with iron oxide nanoparticles[END_REF][START_REF] Wu | Fluorescence quenching of fulvic acids by fullerene in water[END_REF].

In evaluation of quenching behavior, [START_REF] Luster | Multi-wavelength molecular fluorescence spectrometry for quantitative characterization of copper(II) and aluminum(III) complexation by dissolved organic matter[END_REF] concluded that the different types of bonding of copper metal with OM involved weak bonds, strong bonds, and very strong complex bonds. [START_REF] Smith | Multisite metal binding to fulvic acid determined using multiresponse fluorescence[END_REF] proposed a multiresponse method to explain all the available fluorescence sites of Cu-OM binding, with five different fluorescent components of OM being identified using a spectral resolution technique. The application of statistical methods in fluorescence suppression studies is a useful tool for evaluating intermolecular organic matter and trace metal interactions [START_REF] Yamashita | Characterizing the interactions between trace metals and dissolved organic matter using excitation-emission matrix and parallel factor analysis[END_REF]). In the literature several studies related to fluorescence quenching involving copper and humic substances has been extensively investigated (Esteves da Silva et al. 1998;Plaza et al. 2005;Hernández et al. 2006;[START_REF] Bai | Ultraviolet absorbance titration for determining stability constants of humic substances with Cu (II) and Hg (II)[END_REF][START_REF] Chen | Influence of water chemistry and dissolved organic matter (DOM) molecular size on copper and mercury binding determined by multiresponse fluorescence quenching[END_REF][START_REF] Fuentes | Main binding sites involved in Fe(III) and Cu(II) complexation in humic-based structures[END_REF][START_REF] Zhu | Characterizing the interaction between uranyl ion and soil fulvic acid using parallel factor analysis and a two-site fluorescence quenching model[END_REF][START_REF] Boguta | Effects of selected chemical and physicochemical properties of humic acids from peat soils on their interaction mechanisms with copper ions at various pHs[END_REF][START_REF] Hu | The effect of anthropogenic impoundment on dissolved organic matter characteristics and copper binding affinity: Insights from fluorescence spectroscopy[END_REF][START_REF] Huang | Investigating binding characteristics of cadmium and copper to DOM derived from compost and rice straw using EEM-PARAFAC combined with two-dimensional FTIR correlation analyses[END_REF]. Fewer studies have investigated the interactions between humic substances and aluminum [START_REF] Gerke | Aluminum complexation by humic substances and aluminum species in the soil solution[END_REF][START_REF] Smith | Multisite metal binding to fulvic acid determined using multiresponse fluorescence[END_REF]. The interactions of humic substances with aluminum are of great interest in research concerning Spodosols, since natural organic matter plays a crucial role in the transport of aluminum and iron along the depth profile [START_REF] Santos | Structure of Humic Substances from Some Regions of the Amazon Assessed Coupling 3D Fluorescence Spectroscopy and CP/PARAFAC[END_REF][START_REF] Tadini | Evaluation of the roles of metals and humic fractions in the podzolization of soils from the Amazon region using two analytical spectroscopy techniques[END_REF]. In this study will show a new data treatment model for fluorescence suppression in soil samples based on the Ryan and Weber model in humic fractions extracted from Amazonian soil. In addition, it will provide quantitative data on complexation capacity and concentration of binding sites, as well as the determination of the conditional stability constant for each component responsible for fluorescence. Therefore, the aim of this study was to evaluate the interactions of humic and fulvic acid samples from an Amazonian Spodosol with Cu(II) and Al(III) ions, using canonical polyadic/parallel factor analysis (CP/PARAFAC) and fluorescence quenching spectroscopy.

Materials and Methods

Study area

The soil samples were obtained from a site located in the north of the municipality of Barcelos,near the Demeni River (0° 15' 18''N;62° 46' 36''W) in the Middle Negro River Watershed region in the Amazon plains of Brazil. According to the Brazilian Institute of Geography and Statistics (IBGE, 2012), the soils in this region are classified as Spodosols. The soils collected were as follows: (a) a permanently waterlogged podzol (P1: 0-350 cm); (b) a seasonally waterlogged podzol (P2: 0-290 cm; P3: 0-350 cm); and (c) a well-drained podzol (P4: 0-390 cm). Further details can be found in a previous publication [START_REF] Tadini | Soil organic matter in podzol horizons of the Amazon region: Humification, recalcitrance, and dating[END_REF].

Extraction and purification of the humic fractions

The extraction and purification of the humic and fulvic acids followed the recommendations of the International Humic Substances Society (IHSS) and [START_REF] Swift | Organic matter characterization[END_REF], as described in detail by [START_REF] Tadini | Evaluation of the roles of metals and humic fractions in the podzolization of soils from the Amazon region using two analytical spectroscopy techniques[END_REF].

Elemental analysis

For elemental analysis of the carbon and nitrogen contents of the materials, 3 mg portions of humic or fulvic acid were weighed out in tin capsules, using an analytical balance. The samples were analyzed by combustion at 1000 °C, employing an elemental analyzer (Model 2400, PerkinElmer). This procedure was performed in duplicate.

Fluorescence spectroscopy

Sample preparation

The studies involving the interactions with the Cu(II) and Al(III) ions were performed using 8.0 mg L -1 of HA or FA in buffered medium with pH of 4.0-5.0. The titration experiments were prepared in sixteen fluorescence cuvette adding different concentration of metal solutions. The metal solutions employed in this study were CuSO4.5H2O (0.01 mol L -1 ) and Al2(SO3).18H2O (0.01 mol L -1 ). The concentrations of the Cu(II) and Al(III) ions added to the solutions of the humic fractions varied from 0 to 105.9 mg L -1 for each metal employed.

Excitation emission matrix (EEM)

Fluorescence measurements were performed with a luminescence spectrometer (Model F4500, Hitachi). The spectra were acquired in the scanning ranges 240-700 nm for emission and 220-510 nm for excitation. The excitation and emission slits were fixed at 10 nm, the integration was set at 500 scans min -1 , and the detector voltage was 700 V. The data were obtained with an open filter and excitation wavelength increases of 10 nm, giving 30 scans. The EEM obtained using this technique was treated using the mathematical method known as canonical polyadic/parallel factor analysis (CP/PARAFAC) [START_REF] Bro | PARAFAC. Tutorial and applications[END_REF][START_REF] Mounier | Copper complexing properties of dissolved organic matter: PARAFAC treatment of fluorescence quenching[END_REF][START_REF] Luciani | How to correct inner filter effects altering 3D fluorescence spectra by using a mirrored cell[END_REF][START_REF] Nouhi | Timeresolved laser fluorescence spectroscopy of organic ligands by europium: Fluorescence quenching and lifetime properties[END_REF].

Results and Discussion

Treatment of the EEM with CP/PARAFAC provided an EEM response model with components representing the contributions to the sample fluorescence signal. The results are presented in Table 1 for the four Amazonian Spodosol profiles. The parameter used to define the best number of components is known as the core consistency diagnostic (CORCONDIA). In this study the values ranging from 95.30 to 98.96% for the humic acids and from 93.93 to 99.88 % for the fulvic acids, in the presence of Cu(II) ions. In the presence of Al(III) ions, the values were from 97.19 to 99.57% for the HA and from 95.60 to 99.65% for the FA. These data were obtained for the CP/PARAFAC models with numbers of components ranging from 2 to 3. The model presenting the greatest number of components with CORCONDIA values over 60% was chosen as the best one for each data set. For all the quenching experiments, the best model had two components, C1 and C2 as shown in Table 1.

P3

Table 1 presents the main components obtained by CP/PARAFAC for the interactions of the humic and fulvic acid samples from the Amazonian Spodosols with the Cu(II) and Al(III) ions. In the literature (Luciani et al. 2009;[START_REF] Mounier | Copper complexing properties of dissolved organic matter: PARAFAC treatment of fluorescence quenching[END_REF][START_REF] Santos | Structure of Humic Substances from Some Regions of the Amazon Assessed Coupling 3D Fluorescence Spectroscopy and CP/PARAFAC[END_REF] its considered that the more the emission wavelength was blue-shifted, the more the component was condensed and aromatic. In this study the Components B, C, D, and F presented double excitation maxima, which could be attributed to different energy levels of the chromophores or to different excitation moieties present in the molecular structures leading to the same emission function.

For a better knowledge of components obtained by CP/PARAFAC, Table 1 shows the descriptions of the components, as such as, denomination A was assigned to peak A, typical of humic-like substances; denomination B was low energy emission peaks typical of terrestrial humic acid; denomination C referred to peaks A and C, which are characteristic of humic substances from terrestrial environments, with peak A being related to fulvic acid and peak C being related to humic acid; denomination D and F referred to peak D, corresponding to fulvic acids of soils; and denomination E referred to the T peak of the tryptophan protein [START_REF] Coble | Characterization of marine and terrestrial DOM in seawater using excitation-emission matrix spectroscopy[END_REF][START_REF] Matthews | Excitation-emission-matrix fluorescence spectroscopy applied to humic acid bands in coral reefs[END_REF][START_REF] Stedmon | Tracing dissolved organic matter in aquatic environments using a new approach to fluorescence spectroscopy[END_REF][START_REF] Coble | Aquatic Organic Matter Fluorescence[END_REF]). The humic acids showed only two components,

A and B (Table 1) for all profile study, while the fulvic acid samples exhibit three components that varied between profiles, as shown Table 1.

Evaluation was made of two different metal complexation models, namely the 1:1 and 1:2 models [START_REF] Ryan | Fluorescence quenching titration for determination of complexing capacities and stability constants of fulvic acid[END_REF]. The 1:1 model is represented by the following equation:

L1 + M ↔ ML1 (1)
where L1 is a free complexing site, ML1 is the complex, and M is the free metal (Cu or Al). This chemical reaction is controlled by the conditional equilibrium constant and the mass balance:

K1 = [ML1] / [L1] [M] (2) CL1 = [ML1] + [L1] (3) M0 = [ML1] + [M] (4)
The 1:2 model considers that for a single sample, there are two independent types of complexing site present at the same time. This model is represented by the following equations:

L1 + M ↔ ML1 and L2 + M ↔ ML2 (5)
where L1 and L2 are complexing sites, ML1 and ML2 are the metal complexes with sites L1 and L2, respectively, and M = Cu or Al. This chemical reaction is controlled by the conditional equilibrium constant and the mass balance:

K1 = [ML1] / [L1] [M] and K2 = [ML2] / [L2] [M] (6) CL1 = [ML1] + [L1] and CL2 = [ML2] + [L2] (7) M0 = [ML1] + [ML2] + [M] ( 8
)
where CL1 and CL2 are the total complexation sites present in the sample. Assuming that L1, L2, ML1, and ML2 have fluorescence quantum yields of ΦL1, ΦL2, ΦML1, and ΦML2, respectively, it is possible to calculate the theoretical fluorescence responses depending on the parameters IF1:1 = f(L1, K1, M0) and IF1:2 = f(L1, L2, K1, K2, M0), and to fit them minimizing the following functions:

BIAS1:1 = Σ[(IFi-IF1:1(CL1,K1,M0i)/IFi]^2 (9) BIAS1:2 = Σ[(IFi-IF1:2(CL1,CL2,K1,K2,M0i)/IFi]^2 (10)
where IFi and M0i are the component contribution and the total metal concentration obtained with addition of the metal, respectively. The equations were adjusted using a simplex algorithm with positive constraints on all the parameters, performed with a modified "fminsearch" Matlab script (Matlab 2012Ra) obtaining two models. So, these discrete models of complexation were chosen because they are fast and are useful for a rapid overview of the complexant properties. Figure 1 shows the BIAS1:1 and BIAS1:2 models for component 1 (Figure 1a) and component 2 (Figure 1b) for the interactions of the HA and FA with Cu(II). As shown in Figure 2, most of the fulvic acid samples showed higher conditional stability constant (K) values for CP/PARAFAC component 1 (Table 1).

This component corresponded to a molecule with simpler structure that could be related to components described in the "C/E" and "C/D" chart (as shown in Table 1), with correlation to component C of the FA (the component with emission more towards the blue region, reflecting the presence of aliphatic groups). In the case of the humic acid samples (Figure 2), different behavior was observed, with the highest values of K for component 2, which represents more complex structures with emission in the red region (corresponding to denomination "B" in Table 1). The humic substances samples presented as a group gathered near the identity line, with a K value of around 50,000 mol -1 L. These results indicated that for copper, the HA were more complexing and more homogeneous, compared to the FA, for which there was greater spread, with K values ranging from 500 to 50,000 mol -1 .L.

The same study was carried out using Al(III) ions. The BIAS values obtained by the mathematical models are shown in Figure 3. It can be observed that the best mathematical model representing the interaction of Al(III), specially humic acids was the 1:1 model, because all the points were low BIAS for the Component 1 (Figure 3).

Interestingly, the difference between the two models was more marked for Al(III) than for Cu(II), and comparison of the BIAS values showed that those obtained for Al(III)

were significantly lower than those for Cu(II), as shown in Figure 1a. Figure 4 shows the behavior of the conditional stability constant (K) for the interactions of Al(III) with the humic fractions. The fulvic acids presented higher values of K for component 1, compared to the humic acids, with the latter showing little differentiation between components C1 and C2 (Table 1), as shown in Figure 4. As shown in Figure 4, the highest conditional stability constant values were shown by the fulvic acid samples for component 1 (1000 mol -1 .L), especially for the components denoted "C/E" and "C/F" (Table 1), whose characteristics corresponded to compounds with more aliphatic or less condensed structures, emitting fluorescence in the blue region. The humic acid samples did not present any substantial difference between components C1 and C2. The conditional stability constant values again showed less spread, compared to the values for the FA.

The numbers of sites able to complex the metals were determinate the complexation capacity ligand (CL) for the Components 1 and 2. This parameter was obtained by adding the CL1 and CL2 values of the components and dividing by the carbon content of the corresponding sample. The CL represents the density of complexing sites (in mol of complexing sites) for a metal (Cu or Al) per mol of carbon in the organic matter fractions. Figure 5 shows the CL values for the humic fractions, with respect to the metal ions Cu(II) and Al(III), with BIAS1:1 as a proxy of fitting error. Figure 5, the average CL values were 1.18 10 -9 to 2.40 10 -8 for the humic and fulvic acids for Cu(II), respectively; and for Al(III), the average values were and 1.26 10 -10 to 1.26 10 -9 for the HA and FA, respectively. It can be seen from Figure 5 that the densities of complexation sites for Cu(II) and Al(III) presented similar behaviors, since most of the horizons were grouped at around 4.00 10 -10 and 5.00 10 -9 , respectively.

The results showed that the complexation capacity (considering the carbon content) was 10 times lower for the humic acid samples (scale in 10 -10 ) than for the fulvic acids (scale in 10 -9 ), as shown in Figure 5. The results shown that the humic acids required 10 times more carbon in their structures, in order to have the same complexing site density as the fulvic acids present in Spodosol Amazonian. Hence, the fulvic acid shown to have a greater quantity of complexation sites available to interact with the Cu(II) and Al(III) ions, as shown in Figure 5. Results obtained in this work corroborate with study realized by [START_REF] Mounier | Copper complexing properties of dissolved organic matter: PARAFAC treatment of fluorescence quenching[END_REF], that used the fluorescence quenching in black water from Rio Negro-Brazil and they showed that PARAFAC enables quantitative evaluation of complexing parameters for copper, and a good multi-response methods. and Al(III), respectively. These values were lower than those reported in previous studies (Esteves da Silva et al. 1998;Plaza et al. 2005;Hernández et al. 2006;Funtes et al. 2013), showing that the humic substances present in the Amazonian soil contained greater quantities of bonding groups in their structures. The greatest affinities were shown by the fulvic acid samples, which had the highest concentrations of sites available for binding to Cu(II) and Al(III).

Esteves da

Esteves da [START_REF] Esteves Da Silva | Characterization of the binding sites for Al(III) and Be(II) in a sample of marine fulvic acids[END_REF] studied the interaction of Al(III) with fulvic acids from marine samples, employing synchronous fluorescence spectroscopy with evolving factor analysis, obtaining a conditional stability constant of log10K = 5.10 at pH 4.

According to Esteves da [START_REF] Esteves Da Silva | Characterization of the binding sites for Al(III) and Be(II) in a sample of marine fulvic acids[END_REF], the concentration of binding sites for marine fulvic acid samples was less than half of that for soil fulvic acid samples, suggesting existence of common pathways in the humification processes occurring in the soil and aquatic system.

Figure 6 shows the correlation between the complexation capacities to the Cu(II)

and Al(III) the humic fractions of the soil horizons and profiles evaluated in this study.

It can be seen that the humic acid samples presented lower scattering for Al(III), indicative of a constant density of Al(III) sites, while the density of Cu(II) sites varied.

The HA appeared to have a constant specific density of complexing sites for Al(III), while the FA showed no such specificity, since the complexing capacity varied linearly for both Cu(II) and Al(III), maintaining the same ratio between the concentrations of complexing sites for the ions studied. A final treatment of the data was performed using principal component analysis (PCA) (Figure 7). The results (Figure 7) showed clear separation of the humic fractions.

The points for the humic acids were more clustered, while those for the fulvic acids were more dispersed. This separation was due to the influence of the complexing capacity, with the grouping of the humic acids reflecting the lower complexing capacity values. In addition, the best separation occurred to profile for the fulvic acid samples, but some of the FA horizons presenting very different characteristics and the most distant corresponding to the profiles P4 and P3. The differentiation between the FA and HA was mainly due to the physical-chemical properties related to Al(III), corroborates with the study of [START_REF] Boguta | Effects of selected chemical and physicochemical properties of humic acids from peat soils on their interaction mechanisms with copper ions at various pHs[END_REF]. The authors showed that the conditional stability constant obtained for HA-Cu(II) complexes correlated with some of the physicalchemical properties of the humic fraction, such as the predominance of -COOH and -OH groups. The authors suggest that had been increased stability of the complexes, and this group was associated with increase in the content of oxygen-containing structures, indicating the formation of highly stable chelation complexes involving HA-Cu(II) bonds, which presented greater stability when compared to simple and monodentate complexes. Humic acids with high molecular weights and highly condensed aromatic units tend to have higher affinity for binding with the Cu(II) ion (Plaza et al. 2005;[START_REF] Boguta | Effects of selected chemical and physicochemical properties of humic acids from peat soils on their interaction mechanisms with copper ions at various pHs[END_REF]). The literature reports few studies concerning quenching analysis of fulvic acids, as shown in Table 2. There have been no previous studies related to the fluorescence quenching of humic and fulvic acids extracted from Amazonian soils with Cu(II) and Al(III), indicating the novelty of the present work. Plaza et al. (2005) determined the stability constants (logK) and complexation capacities (CC) for Cu(II) ions, using humic and fulvic acids extracted from soils that had received pig waste fertilization (Table 3). It was found that Cu(II) presented higher binding affinity for HA, compared to FA. Furthermore, the application of pig waste to the soil decreased the Cu(II) binding affinity for the humic fractions. The low values of CC and logK for the humic and fulvic acids from soil fertilized with pig waste, as well as for the fulvic acid from soil without fertilization, were suggested to be associated with the presence of simple structural components with low degrees of humification and low molecular weights. On the other hand, the higher values of CC and logK could be associated with organic material with higher aromatic condensation, greater humification, and higher molecular weight. The authors concluded that the presence of more stable organic material with a higher degree of humification increased the affinity for the Cu(II) ion.

The interaction of humic fractions of the Amazonian Spodosols with Cu(II) and Al(III) ions showed that HA presented smaller amounts of complexation sites and a lower stability constant when compared to FA according to Table 2. Fulvic acids showed higher complexation capacity, which may be associated with their simpler chemical structure, which allows a greater selectivity of interaction with these metals.

Whereas, humic acids presented a more complex structure and their metal selectivity was lower as determined by the low complexation capacity.

Studies by [START_REF] Tadini | Evaluation of the roles of metals and humic fractions in the podzolization of soils from the Amazon region using two analytical spectroscopy techniques[END_REF] using the same soils presented in this work, showed that the mobilization of suspended organometallic complexes and metallic oxides were controlled by the presence of groundwater outcrops favored the movement of the metals, especially in P1 and P4 profiles. The results showed that the FA fraction were associated with high amounts of Al in the soils, while the HA fraction was more selective towards Fe. The authors concluded that the transfer of Fe and Al in these profiles is due to the type of chemical structure, the movement of the groundwater and the process of formation of this soil. Therefore, it can be inferred that the FA have a contribution from groundwater, whose chemical structure varies little with the soil profile and a greater selectivity in the interaction with the metals, especially with the Al metal. In contrast, HA were less selective because they may be associated with other metals and have a greater variation in chemical structure with soil profile. Due to this diversity of metals that HA has affinity for, it is suggested that they may be responsible for soil fertility. In this case, soils of great environmental relevance such as the present in the Amazon region as discussed in this study.

Conclusions

Investigation of the humic fractions from Amazonian Spodosols showed that the 1:1 model was most suitable for modeling variations of fluorescence quenching with Cu(II) or Al(III). It could be concluded from the results that the humic acids presented only two components, for which the complexing properties did not vary with the soil profile. The fulvic acid samples showed greater variation of these properties according to the profile. For both Cu(II) and Al(III), the CP/PARAFAC components represented typical humic material, with emission wavelengths ranging from 400 to 550 nm. The humic acid samples generally presented complexes with blue shifts (C1), rather than red shifts (C2) and more homogeneous that FA which obtained three different components.

For both metals studied, the humic acids presented smaller quantities of complexation capacity (CL), compared to the fulvic acid samples. The HA showed a more homogeneous of the constant stability and complexation capacity for Al(III), compared to the FA, which were more heterogeneous characteristic for both metals, Cu(II) and Al(III). The results shown that the humic acids required 10 times more carbon in their structures, in order to have the same complexing site density as the fulvic acids, it can be infers that the FA fraction has higher mobility and greater interaction in this Spodosol Amazonian.

Table 1 :

 1 Components obtained by CP/PARAFAC for interactions of the humic acid and fulvic acid samples, extracted from the Amazonian Spodosols, with the Cu(II) and Al(III) ions.

Firstly

  , identification of the best complexation model was achieved by determining which model provided the best fits for the interactions of the humic fractions with Cu(II) and Al(III), by comparing BIAS1:1 (model 1:1) and BIAS1:2 (model 1:2) in terms of the probability of components (C1 and C2) obtained by CP/PARAFAC. Mounier and coauthors (2011) defined BIAS as the sum of the absolute value of the difference between the experimental fluorescence intensity logarithm and the calculated fluorescence logarithm intensity.

Figure 1 :

 1 Figure 1: Comparison of the BIAS1:1 and BIAS1:2 models of the Component 1 (a) and Component 2 (b) for Cu(II). Descriptions of terms -Bias C1_Cu_1:2: Bias for Component 1 by Cu(II) with 1:2 model; Bias C1_Cu_1:1: Bias for Component 1 by Cu(II) with 1:1 model; Bias C2_Cu_1:2: Bias for Component 2 by Cu(II) with 1:2 model; Bias C2_Cu_1:1: Bias for Component 2 by Cu(II) with 1:1 model;

Figure 2 :

 2 Figure 2: Evaluation of the conditional stability constants for the interactions of Cu(II) with the humic acids (highlight blue) and fulvic acids (highlight green), using the 1:1 model, with each Component obtained by CP/PARAFAC. Descriptions of terms -logK_C1_Cu_1:1: logarithm of conditional constant

Figure 3 :

 3 Figure 3: Comparison of the BIAS1:1 and BIAS1:2 values of the Component 1 (a) Component 2 (b) for Al(III). Descriptions of terms -Bias C1_Al_1:2: Bias for Component 1 by Al(III) with 1:2 model; Bias

Figure 4 :

 4 Figure 4: Evaluation of the conditional stability constant for the interactions of Al(III) with the humic acids (highlight blue) and fulvic acids (highlight green), using the 1:1 model, with each component obtained by CP/PARAFAC. Descriptions of terms -logK_C1_Al_1:1: logarithm of conditional stability

Figure 5 :

 5 Figure 5: Comparison between the CL (CL1 + CL2) values of the humic and fulvic acids, for Cu(II) ions (highlighted in blue) and Al(III) ions (highlighted in red), with the BIAS shown by the error bars of the samples.

  Silva et al. (1998) used the Stern-Volmer model to determine logK for the interactions of Cu(II) with humic and fulvic acids extracted from soil in Galicia (Spain). The conditional stability constant (log K) was 4.60 and higher values for the conditional stability constants were obtained for the samples with higher concentrations of FA (100 mg/L, pH = 6.0). It was concluded that the stabilities of the FA-Cu(II) and HA-Cu(II) complexes were directly related to the numbers of binding sites present in the structures of the humic substances. In the present work, the values of logK for the HA were in the ranges 3.79-5.32 and 2.43-4.29 for Cu(II) and Al(III), respectively. The corresponding values for the FA were in the ranges 2.26-5.31 and 1.80-4.14 for Cu(II)

Figure 6 :

 6 Figure 6: Correlation between the complexation capacities (CL1 + CL2) of the Amazonian Spodosol humic fractions for the Al(III) and Cu(II) ions. Descriptions of terms -♦P1_HA: Profile 1 for Humic Acid; ■P2_HA: Profile 2 for Humic Acid; ▲P3_HA: Profile 3 for Humic Acid; ■P4_HA: Profile 4 for Humic Acid; ♦P1_FA: Profile 1 for Fulvic Acid; •P2_FA: Profile 2 for Fulvic Acid; •P3_FA: Profile 3 for Fulvic Acid and ▲P4_FA: Profile 4 for Fulvic Acid;

Figure 7 :

 7 Figure 7: Principal component analysis (PCA) of the quenching analysis results for the humic and fulvic acid samples, represented by profiles. Descriptions of terms -CL1_Al: Complexation Capacity for Component 1 by Al(III) ions; CL2_Al: Complexation Capacity for Component 2 by Al(III) ions; CL1_Cu: Complexation Capacity for Component 1 by Cu(II) ions; CL2_Cu: Complexation Capacity for Component 1 by Cu(II) ions; K_C1_Al_1:1: Conditional stability constant for Al(III) by Component 1 for 1:1model; K_C2_Al_1:1: Conditional stability constant for Al(III) by Component 2 for 1:1model; K_C1_Cu_1:1: Conditional stability constant for Cu(II) by Component 1 for 1:1model; K_C2_Cu_1:1: Conditional stability constant for Cu(II) by Component 2 for 1:1model;■ P1_HA: Profile 1 for Humic Acid; •P2_HA: Profile 2 for Humic Acid; ▲P3_HA: Profile 3 for Humic Acid; ♦P4_HA: Profile 4 for Humic Acid; □P1_FA: Profile 1 for Fulvic Acid; ○P2_FA: Profile 2 for Fulvic Acid; ∆P3_FA: Profile 3 for Fulvic Acid and ◊P4_FA: Profile 4 for Fulvic Acid.

  Therefore, this work allowed us to show a new data treatment model for fluorescence suppression in soil samples, using the Ryan-Weber model and CP/PARAFAC, obtaining quantitative data for EEM. A similar study was described by Zhu and coauthors (2014) showed a new fluorescence suppression treatment based on the Ryan-Weber model using the interaction of Cu(II) ions with tryptophan and tyrosine. According to the authors modeling techniques are necessary to understand the phenomenon of complexation that occurs in organic matter. Hence, the sensitivity and simplicity of the fluorescence technique combined with statistical treatments capable of analyzing interactions with metals at the molecular level (Esteves da Silva et al. 1998).

Table 2 :

 2 Conditional stability constants (logK) and complexation capacities (CL) reported in the literature.

		Soil	Metal	Method	Conditional stability constant (logK)	Complexation capacity (CL / mmol g -1 )	Reference
		Amazonian Spodosol	Cu(II)	Ryan-Weber	3.79 -5.32	0.01 -0.13	This study
		Amazonian Spodosol	Al(III)	Ryan-Weber	2.43 -4.29	0.02 -0.05	This study
		Calcic Luvisol	Cu(II)	Scatchard	6.02 -7.04	0.22 -0.86	Plaza et al. 2005
	Humic Acid	EUROSOILS Calcic Luvisol Peat and Leonardite	Cu(II) Cu(II) Cu(II)	Ryan-Weber Ryan-Weber Ryan-Weber	5.14 -5.36 4.71 -5.25 4.58 -5.10	1.80 -3.70 1.01 -2.84 0.21 -1.33	Plaza et al. 2005 Hernández et al. 2006 Fuentes et al. 2013
		Peaty-muck	Cu(II)	Ryan-Weber	5.28 -5.38 (pH 5) 5.46 -5.77 (pH 7)	0.10 -0.30 (pH 5) 0.27 -0.42 (pH 7)	Boguta et al. 2016
		Amazonian Spodosol	Cu(II)	Ryan-Weber	2.26 -5.31	0.11 -2.44	This study
	Fulvic Acid	Amazonian Spodosol Oak Forest	Al (III) Cu(II)	Ryan-Weber Ryan-Weber	1.80 -4.14 4.33 -4.60	0.07 -2.08 0.03 -0.04	This study Esteves da Silva et al. 1998
		Calcic Luvisol	Cu(II)	Scatchard	5.96 -6.41	0.20 -0.52	Plaza et al. 2005

Acknowledgments

The authors are grateful for the financial support provided by the São Paulo State Research Foundation (FAPESP, grant numbers 2011/03250-2, 2012/51469-6, 2013/07276-1, and 2013/13013-3), the Brazilian National Council for Technological and Scientific Development (CNPq, grant number 232225/2014-1-SWE), and the French ANR (Agence Nationale de la Recherche, grant number ANR-12-IS06-0002 "C-PROFOR"). We also thank Embrapa Agricultural Instrumentation for supporting the development of the research. The authors would like to thank Dr. Célia Regina Montes (ESALQ/USP, Piracicaba, São Paulo) for providing samples for analysis.