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.
Asked By : templatetypedef
Answered By : mdxn
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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63422
0 comments:
Post a Comment
Let us know your responses and feedback