16
$\begingroup$

I was reading a question over at Stack Overflow asking whether it was NP-hard to list all simple cycles in a graph containing a particular node and it occurred to me that I couldn't think of any existing complexity class that was well-suited for talking about problems of the form "list all solutions to this problem." The class NP in some sense consists of problems that ask whether at least one solution exists, the class FNP asks to produce a single solution, and the class #P asks to count how many solutions there are, yet none of these deal with the complexity of exhaustively enumerating all possible solutions.

Is there a complexity class for describing problems that are of the form "given a polynomial-time computable predicate $P(x, y)$ and a string $x$, enumerate all $y$ for which $P(x, y)$ is true subject to [insert some appropriate complexity restrictions]?" I understand that it might be tricky to pin down the restrictions given that the number of solutions might be exponentially larger than the size of the input $x$, though that doesn't seem insurmountable.

$\endgroup$
6
  • $\begingroup$ Interesting. Maybe in practice too many instances of relevant problems often have an exponential number of solutions, if any. Instances for SAT and CLIQUE, in general, have a large solution space. $\endgroup$
    – chi
    Sep 13, 2016 at 17:14
  • 3
    $\begingroup$ Here's another ansatz for formalizing this. A problem $P$ is in $XE$ (for X-enumerable) if there is an X-algorithm $A$ with so that $A(x,i)$ returns the $i$th solution (i.e. the $I$th $y$ with $P(x,y)$) w.r.t. some ordering. Note how this is similar to how one sometimes defines RE. This circumvents the size of the solution space and focuses on how hard finding the next solution is. The total cost is available by summation, of course. $\endgroup$
    – Raphael ♦
    Sep 13, 2016 at 21:05
  • 3
    $\begingroup$ (I've never seen it defined as a class, but are you aware of the concept of enumeration with polynomial delay?) ​ ​ $\endgroup$
    – user12859
    Sep 13, 2016 at 23:35
  • $\begingroup$ @Raphael This may not be what we are looking for. For example, if the best algorithm for $A(x,i)$ has to iterate over all solutions until it has found $i$ of them and runs in time $\Theta(f(|x|))$, then the complexity we are looking for is $\Theta(f(|x|))$, but summation would suggest complexity $\Theta(f(|x|)^2)$. $\endgroup$
    – Lieuwe Vinkhuijzen
    Sep 17, 2016 at 21:45
  • $\begingroup$ @RickyDemer That's what I was shaking out of my sleaves, isn't it? Good to know that there's an established formalization. $\endgroup$
    – Raphael ♦
    Sep 19, 2016 at 13:57

1 Answer 1

Reset to default
11
+150
$\begingroup$

The concept you are looking for is called enumeration complexity, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a language/set). Enumeration algorithms can be modeled as a two step process:a precomputation step and an enumeration phase with delay. Both of these steps have their own time and space complexities (perhaps entropy, too). In the general spirit of complexity, there are often trade offs between these to consider.

The precomputation step performs some work that is necessary before the first solution is enumerated. This might involve finding the solution itself or initializing some large data structure that will reduce the overall delay between each solution.

The delay is the resource cost associated with the computation necessary in between arbitrary enumerated solutions. In other words, the delay is a measure of the space and time needed to produce the $i+1^{th}$ solution after the $i^{th}$ one. Problems whose solutions that take $O(1)$ time for each enumeration are said to have constant delay. A requirement of $O(poly(n))$ time is said to have polynomial delay.

For the enumeration problem you specifically mentioned in your question, you should look into the class $ENUM_{NP}$ and its related siblings in section 2.1 of "Enumeration: Algorithms and Complexity" by Johannes Schmidt (Linked at the bottom).

Why do we care about precomputation time and delay?

Delay is very key to understanding the true intricacies of enumeration problems. Enumerating the elements of $\Sigma^*$ (up to size $n$) and $\{ \vec{x} : \phi(\vec{x}) \}$ where $\phi(\vec{x})$ is a Boolean formula (i.e. SAT) both take exponential time. However, enumerating through $\Sigma*$ only requires constant delay since you can just go through the elements in some order. For all we know, the delay for enumerating solutions to a 3SAT instance could be exponential. Our job as complexity theorists is to capture why the latter problem is fundamentally harder (more complex) than the former one. Delay does a pretty good job at showcasing this difference.

Likewise, we also need to know how much precomputation is done. We can reduce the delay for any enumeration problem to constant time and space by precomputing all solutions and storing them in a list to be enumerated at a later time. The challenge is to find the best balance between the two resources.

The order in which you enumerate the elements can also influence the complexity. Requiring results to be returned in a specified sorted order might require us to perform additional computation in both steps. Though situations where any order suffices (as long as each enumerated element is unique) are certainly studied, too.

As far as I know, these classes do not typically have concise labels (akin to $P$ and $NP$). We cannot feasibly expect to be able to do this since enumeration complexity classes are juggling around 3 or more resources (precomputation/total time, space, delay, and entropy). There are simply too many combinations of resource bounds to hand out special names. This does not make these classes any less interesting and also does not stop researchers from trying anyways.

Resources

This survey (really an attempt at formalization) should help you get started. It also proves some basic hierarchy theorems.

Enumeration: Algorithms and Complexity (Johannes Schmidt, 2009)

https://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/schmidt-da.pdf

For an enumeration of results in enumeration complexity, check out this compilation curated by Kunihiro Wasa. Since it is categorized by problem type, you can easily find a number of papers dedicated to enumerating graph cycles. It should be simple to modify the algorithms involved to only consider cycles with a given node.

http://www-ikn.ist.hokudai.ac.jp/~wasa/enumeration_complexity.html

$\endgroup$
2
  • $\begingroup$ Would I be right in thinking that enumerating the elements of $\Sigma^*$ up to size $n$ with $O(1)$ delay would require them to be output in Gray code order? Or is it normally assumed in the area of enumeration complexity that writing out one solution takes $O(1)$ time, even if the space needed for storing the solution is larger than that? $\endgroup$
    – j_random_hacker
    Sep 19, 2016 at 12:42
  • 1
    $\begingroup$ @j_random_hacker I don't think your thinking is wrong, though the real answer to your question is "it depends". The authors of these papers usually indicate which model of computation (regular tape TM vs. RAM vs. Word RAM) they are using. This choice will change what can be considered a constant time operation and what can't (such as incrementing a number or generating output). This difference is presumed to disappear as soon as your delay becomes polynomial due to the extended Church Turing thesis. $\endgroup$
    – mdxn
    Sep 20, 2016 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.