Notation

Let $A(x,y)$ be a set.

Problem $EnumA$: output $A(x,\_):=\{y \mid A(x,y)\}$ on input $x$.

$y \in A(x,\_)$ will be called a solution of (the problem) $A$ on input $x$.

Main Assumption

In this talk, $A$ is an $NP$-predicate, that is:

• $y \in A(x,\_)$ can be tested in polynomial time.
• $y$ is of size polynomial in the size of $x$.

Complexity

How to measure the complexity of an algorithm solving an enumeration problem?

Total Time

Total time needed to output every solution.

There can be exponentially many.

$EnumA$ is in $OutputP$ if it can be solved in time polynomial in:

• $|x|$
• and $|A(x,\_)|$

Delay

Total time is not always satisfactory:

• Process solutions in a stream.
• Only peek at the solution set.

Delay: the longest time one has to wait between the output of two solutions.

Holy $DelayP$ Grail

One focus in enumeration complexity has been to design algorithms with polynomial delay.

1. Guarantees a resonnable waiting time before next solution.
2. Gives a $t \times delay$ upper bound on the time needed to output $t$ solutions.

Linear Incremental Time

Algorithms such that for every $t$, after $t\cdot d(n)$ steps, the algorithm has output at least $t$ solutions.

We say that $d(n)$ is the incremental delay.

$DelayP$ vs $IncP_1$

Clearly $DelayP \subseteq IncP_1$: after $delay \times t$, at least $t$ solutions output.

(Naive) Regularization

Given an $IncP_1$-enumerator $A$ with incremental delay $d$, one can regularize the delay using a queue to delay the output of solutions every $d$ steps:

step = 0
q = Queue()
while(A is not finished):

    move(A)
    step += 1

    if A outputs x:
        q.add(x)

    if step == d:  
        output(q.pull()) 
        step=0 

output(q) # output what remains in q

$IncP_1 = DelayP$

When the simulation of $A$ reaches step $2^n$:

• pushed $2^n$ solutions in the queue
• pulled $2^{n}/2$ of them
• $2^n/2$ remains…

Natural notion in data structure

Suppose enumeration algorithm $A$ works as follows:

• $A$ maintains a dynamic array $T$
• $A$ performs insert/deletion on $T$ between two outputs

Related work 1: Goldberg’s Thesis

• $IncP_1$ = polynomial cumulative delay in L. A. Goldberg’s Thesis (1991)

Related work 2: Any-k Algorithms

Problem: given $k \in \mathbb{N}$, a weighted DAG $G$ and nodes $s,t$, enumerate the paths from $s$ to $t$ ordered by weight.

Wrap up on $IncP_1$

• Incremental delay better than (worst case) delay.
• Better analysis tools using amortized complexity of data structure.

If you do not agree, $IncP_1 = DelayP$ anyway…

Main contribution

Demo first

Detailed Statement

For every $IncP_1$-enumerator $A(x)$ with $N$ solutions:

• incremental delay $d$,
• space $s$,
• total time $T$

there exists a $DelayP$-enumerator with

• delay $O(d \log(N))$
• space $O(s \log(N))$
• total time $O(T)$

Geometric Amortization

• Maintain $l+1=\lceil \log(N) \rceil$ simulations $A_0, \dots, A_l$ of $A$
• $A_i$ outputs solutions for steps in $[2^id;2^{i+1}d[$.
• $A_{i+1}$ “moves faster” than $A_i$.

Faster how?

• $A_i$ moves by at most $2d$ steps.
• If $A_i$ finds a solution in its zone, outputs it and proceed back with $A_l$.
• Otherwise, proceed with $A_{i-1}$.
• Stops when $A_0$ is out of its zone.

Key Lemmas

1. If $A_0, \dots, A_i$ have output $k$ solutions, $A_{i+1}$ has moved by at least $2dk$ steps.
2. There are at least $2^i$ solutions in $[0; 2^id]$.

Delay

Between two outputs:

• each process $A_i$ moves by at most $2d$ steps,
• at most $l = \log(N)$ processes,
• step counters are incremented / compared (to check whether $A_i$ is in zone $[2^i \cdot d; 2^{i+1}\cdot d]$

Simulating RAMs and Counters

• Simulating RAM: With bounds on incremental delay, space and number of solutions of $A$: $O(1)$ to simulate one step.

• Counters: of size at most $\log(dN)$

Gives a $O(d\cdot\log(dN)^2)$ delay (polynomial).

Improvements

Previous algorithm assumes knowledge of (at least an upper bound):

1. $N$, number of solutions of $A(x)$
2. $s$, space used by $A(x)$
3. $d$, Incremental delay of $A(x)$

Unknown incremental delay I

Goal:

• Construct $REG$, taking as input a black box oracle access to an enumerator $A$; the incremental delay $d_A$ is unknown.
• $REG(A)$ outputs the same solutions as $A$ with delay $\alpha \cdot d_A$.
• Can $\alpha$ be independent on $A$ (constant)?

Unknown incremental delay II

For every $\varepsilon$, one can construct $REG$ such that $REG(A)$ has delay $d_A^{1+\varepsilon}$.

Incremental time

The approach generalizes to collapse the following classes:

• Usual $k$-incremental time: the delay between solution $i$ and $i+1$ is $O(poly(n) i^k)$.
• Relaxed $(k+1)$-incremental time: for every $i$, at least $i$ solutions have been output after time $poly(n)i^{k+1}$.

Trading average delay with worst case delay

$E(x,\_)$ a self reducible problem :

• $E(x, \_) = \bigcup_{i} E(x_i, \_)$ with $|x_i| < |x|$
• Branch and bound enumeration algorithm $A$ for $E$
  • Polynomial delay
  • Better average delay when branches have a lot of solutions

Example: enumerating DNF models

Problem:

• Input: a DNF $D = \bigvee_{i \leq m}\ S_i$ on variables $x_1,\dots,x_n$
• Output: every satisfying assignments of $x_1,\dots,x_n$ of $D$.

DNF enumeration in strong polynomial delay

Open question: can we solve it with a delay that is polynomial only in the size of the solutions, ie, $n$.

Two conjectures:

• Strong DNF Enumeration conjecture: impossible with a delay with a $o(m)$ dependency. Refuted using Geometric Amortization
• DNF Enumeration conjecture: impossible with a delay $poly(n)$.

DNF enumeration: $O(n^2 m^\mu)$ delay

Branch and bound algorithm has:

1. average delay $O(n^2 \cdot m^\mu)$ with $\mu = 1-\log_2(3)<1$,
2. incremental delay $O(n^2 \cdot m^\mu)$ with $\mu = 1-\log_2(3)<1$,
3. Geometric amortization gives worst case delay $O(poly(n) \cdot m^\mu)$

Conclusion

• New method to make delay regular without exponential space
• Message: incremental delay may be more natural than worst case delay.

Open problem: can we regularize without changing output order?