Notation

Let A(x, y) be a set.

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

y ∈ 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 ∈ 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.

Example:

Enumerate (0 + 1)ⁿ:

• Method 1: Generates every words of length k inductively up to length n and output them.
• Method 2: Start from 0ⁿ, output it and take next word (using Gray Code for example).

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 × delay upper bound on the time needed to output t solutions.

Linear Incremental Time

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

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

DelayP vs IncP₁

Clearly DelayP ⊆ IncP₁: after delay × t, at least t solutions output.

(Naive) Regularization

Given an IncP₁-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₁ = DelayP

When the simulation of A reaches step 2ⁿ:

• pushed 2ⁿ solutions in the queue
• pulled 2ⁿ/2 of them
• 2ⁿ/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₁ = polynomial cumulative delay in L. A. Goldberg’s Thesis (1991)

Related work 2: Any-k Algorithms

Problem: given k ∈ ℕ, a weighted DAG G and nodes s, t, enumerate the paths from s to t ordered by weight.

Wrap up on IncP₁

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

If you do not agree, IncP₁ = DelayP anyway…

Main contribution

Demo first

Detailed Statement

For every IncP₁-enumerator A(x) with N solutions:

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

there exists a DelayP-enumerator with

• delay O(dlog (N))
• space O(slog (N))
• total time O(T)

Geometric Amortization

• Maintain l + 1 = ⌈log (N)⌉ simulations A₀, …, A_l of A
• A_i outputs solutions for steps in [2ⁱd; 2^i + 1d[.
• 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₀ is out of its zone.

Key Lemmas

1. If A₀, …, A_i have output k solutions, A_i + 1 has moved by at least 2dk steps.
2. There are at least 2ⁱ solutions in [0; 2ⁱd].

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ⁱ ⋅ d; 2^i + 1 ⋅ 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 ⋅ log (dN)²) 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 α ⋅ d_A.
• Can α be independent on A (constant)?

Unknown incremental delay II

For every ε, one can construct REG such that REG(A) has delay d_A^1 + ε.

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, _) = ⋃_iE(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 = ⋁_i ≤ m S_i on variables x₁, …, x_n
• Output: every satisfying assignments of x₁, …, 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²m^μ) delay

Branch and bound algorithm has:

1. average delay O(n² ⋅ m^μ) with μ = 1 − log₂(3) < 1,
2. incremental delay O(n² ⋅ m^μ) with μ = 1 − log₂(3) < 1,
3. Geometric amortization gives worst case delay O(poly(n) ⋅ m^μ)

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?