User:MarKroell/sandbox/Complexity of Enumeration Problems

The complexity of an enumeration problem refers to the inherent difficulty of producing the output of an enumeration problem. While decision problems often ask for the existence of a solution to some problem instance, enumeration problems aim at outputting all solutions. To capture the intuition of easy to enumerate problems – despite a possibly exponential number of output values – various notions of tractable and intractable enumeration classes have been proposed over the years.

Enumeration Problem and Algorithm

edit

Let   be a finite alphabet,   be a positive integer and   be a binary relation such that for every   we have  . Given some  , the set   denotes  .
The enumeration problem   is the function that maps every   to the set  . An enumeration algorithm   of   is an algorithm that, in every input  , outputs the set   without any duplicates.

enumeration problem with order?

Computational Model

edit

The runtime and also the space requirements of an enumeration algorithm may be exponential in the input. Therefore, it is common to use the RAM model (rather than Turing machines) as a computational model, because a RAM can access parts of exponential-size data in polynomial time. An example of an enumeration algorithm that depends on the RAM model is the enumeration of all maximal independent subsets of a graph in lexicographic order[1].

Measures of Complexity

edit

The resources that are considered when computing the answers to an enumeration problem are space and time.
The space complexity of an enumeration problem   is given by the total amount of memory that an enumeration algorithm   of   needs to produce all of the answers to   w.r.t. the size of the input.

The time complexity of an enumeration problem is either measured w.r.t the size of the input (input sensitive measure), or w.r.t. of the output (output sensitive measure).

Input Sensitive Measures

edit

Measuring the complexity of an enumeration problem by the size of the input is equivalent to the usual measure of time complexity for function problems. Given an enumeration problem  , input   and a computable function  ,   can be solved within time   if there is an enumeration algorithm that outputs all of the solutions within this time.

cases where this upper bound is not trivial: all minimal dominating sets[2]

Output Sensitive Measures

edit

Given some enumeration problem   over a relation   and an input  , the set of solutions   is exponential in general. Moreover, depending on the enumeration problem itself, the size of the set of solutions can have a high fluctuation range, depending on the input. Therefore it is common to not only use the size of the input to measure the complexity of an enumeration problem, but also the output. The following are the most common approaches to measure the complexity of a problem w.r.t. the output:

Time w.r.t. the size of the complete output

This measure is used when one is interested in producing the full set of solutions R(x) to a instance x. This measure is used in fields such as biology or chemistry[3]

Time w.r.t. the size of some of the output produced so far

When we don't want to wait for all the solutions and the output is large, we might be interested in just a few solutions, but want to have a guarantee at any given time. An enumeration problem is tractable in the context of this measure, if we can output   many solutions in time  . This is equivalent to a continuous output of solutions with an increasing delay, where the delay grows linear in the size of the output produced so far. Moreover, this measuring w.r.t. some output produced at any given point is of special interest if the size of the instance   is significant larger than the size of a single solution. In this case, a valid measure is the time w.r.t. the previous solution that was output[4].

Regularity of the produced solutions

This is in contrast to the measure w.r.t. size of the output produced so far, where the delay between the output continuously grows.

Amortized Complexity

This measurement is concerned with the size of the total time divided by the number of solutions. (kind of regularity) Uno proposed [5] a general method to obtain constant amortized time algorithms, which can be applied, for instance, to find the matchings or the spanning trees of a graph...

Complexity Classes

edit

First EnumP: This is the class of all NP-relations (introduce the check problem?) On the other hand, enumeration problems restricted to NP-relations enjoy better properties, for instance stability by union[6]. It is also the case that the vast majority of enumeration problems that appear in the literature have a corresponding Check problem which is decidable in polynomial time.

For input sensitvie things, do we have a class?

The usual suspects

edit

Let   be an alphabet. Given an enumeration problem   over relation  . The following enumeration complexity classes are defined via the existence of an enumeration algorithm  , satisfying different properties:

  1. OutputP (Output Polynomial Time): The enumeration problem   is in OutputP (also TotalP), if there exists an enumeration algorithm   and a positive integer  , such that for every input  , the algorithm   outputs   in time  . This class is also called Total Polynomial Time (insert citation).
  2. The Inc Hierarchy: [7]
  3. SDelayP (Strong polynomial delay): For some problems, the size of the input may be much larger than the size of the generated solutions, which makes polynomial delay an unsatisfactory measure of efficiency. In that case, algorithms whose delay depends on the size of a single solution are naturally more interesting than polynomial delay or output polynomial algorithm[8]
  4. DelayP (Polynomial Delay): The enumeration problem   is in DelayP, if there exists an enumeration algorithm   and a positive integer  , such that for every input  , the algorithm   outputs the elements   with a regular intervals (the so-called delay), such that the delay between

any consecutive solutions as well as the time before outputting the first solution as well as the time between outputting the last solution and termination of   is bound by  .

  1. DelayClin (Constant Delay after linear preprocessing): Introduced by Durand and Grandjean[9]

Higher Complexity Classes

edit

Hierarchy for higher complexity classes (with motivation?) defined: [10]

  1. DelayP Hierarchy
  2. IncP Hierarchy

Parameterized Complexity

edit

framework in [11]

Relationship among the classes

edit

Either intersected with EnumP or not

Relationship to other Computational Problems

edit

Decision Complexity

edit

the another solution problem, lower bounds (which proves non-membership in outputP) first appears in[12], also used in [13]

Counting Complexity

edit

Some basic results for constant delay stuff?


Functional Complexity

edit

cite new results as given in [14] (TFNP = FP if and only if IncP = OutputP)


Open Problems

edit

The importance of EnumP?

edit

The restriction of classes to EnumP, even though it appears all throughout the literature, seems kind of arbitrary. there are benefits (see the definition of EnumP), however, there are enumeration problems (both natural and artificial ones) with a Check problem outside of Ptime.

Lower Bounds in Complexity

edit

This is the major open problem here. Despite the multitude of different enumeration classes and hierarchies, there are very few tools to show that a problem is in one class but not in a smaller one. Even though there are some notions for reductions (for fine-grained problems, for problems equivalent to the enumeration of the transversals of a hypergraph, or reductions for hard enumeration problems), complete problems for the lower complexity classes are sorely missing. Therefore, we either need to find a notion of reduction that allows for complete problems in classes that we are interested in, or more generally, a set of tools to show lower bounds.

Transversal Hypergraph

edit

problems equivalent: [15] [16] only in output-subexponential time: [17] currently best approach:

References

edit
  1. ^ Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H. (March 1988). "On generating all maximal independent sets". Information Processing Letters. 27 (3): 119–123. doi:https://doi.org/10.1016/0020-0190(88)90065-8. {{cite journal}}: Check |doi= value (help); External link in |doi= (help)
  2. ^ Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem V.; Stepanov, Alexey A. (1 November 2008). "Combinatorial bounds via measure and conquer". ACM Transactions on Algorithms. 5 (1): 1–17. doi:10.1145/1435375.1435384.
  3. ^ Barth, Dominique; David, Olivier; Quessette, Franck; Reinhard, Vincent; Strozecki, Yann; Vial, Sandrine (2015). "Efficient Generation of Stable Planar Cages for Chemistry". Experimental Algorithms. Springer International Publishing: 235–246. doi:10.1007/978-3-319-20086-6_18.
  4. ^ Strozecki, Yann; Capelli, Florent (9 October 2018). "Enumerating models of DNF faster: breaking the dependency on the formula size". {{cite journal}}: Cite journal requires |journal= (help)
  5. ^ Uno, Takeaki (2015). "Constant Time Enumeration by Amortization". Algorithms and Data Structures. Springer International Publishing: 593–605.
  6. ^ Strozecki, Yann (1 January 2010). /2010PA077178 "Enumeration complexity and matroid decomposition". Paris 7. {{cite journal}}: Check |url= value (help); Cite journal requires |journal= (help)
  7. ^ Capelli, Florent; Strozecki, Yann (August 2018). "Incremental delay enumeration: Space and time". Discrete Applied Mathematics. doi:https://doi.org/10.1016/j.dam.2018.06.038. {{cite journal}}: Check |doi= value (help); External link in |doi= (help)
  8. ^ Strozecki, Yann; Capelli, Florent (9 October 2018). "Enumerating models of DNF faster: breaking the dependency on the formula size". {{cite journal}}: Cite journal requires |journal= (help)
  9. ^ Durand, Arnaud; Grandjean, Etienne (1 August 2007). "First-order queries on structures of bounded degree are computable with constant delay". ACM Transactions on Computational Logic. 8 (4): 21–es. doi:10.1145/1276920.1276923.
  10. ^ Creignou, Nadia; Kröll, Markus; Pichler, Reinhard; Skritek, Sebastian; Vollmer, Heribert (March 2019). "A complexity theory for hard enumeration problems". Discrete Applied Mathematics. doi:https://doi.org/10.1016/j.dam.2019.02.025. {{cite journal}}: Check |doi= value (help); External link in |doi= (help)
  11. ^ Creignou, Nadia; Meier, Arne; Müller, Julian-Steffen; Schmidt, Johannes; Vollmer, Heribert (13 September 2016). "Paradigms for Parameterized Enumeration". Theory of Computing Systems. 60 (4): 737–758. doi:https://doi.org/10.1007/s00224-016-9702-4. {{cite journal}}: Check |doi= value (help); External link in |doi= (help)
  12. ^ Lawler, E.; Lenstra, J.; Rinnooy Kan, A. (1 August 1980). "Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms". SIAM Journal on Computing. 9 (3): 558–565. doi:10.1137/0209042. ISSN 0097-5397.
  13. ^ Kavvadias, Dimitris J.; Sideri, Martha; Stavropoulos, Elias C. (May 2000). "Generating all maximal models of a Boolean expression". Information Processing Letters. 74 (3–4): 157–162. doi:https://doi.org/10.1016/S0020-0190(00)00023-5. {{cite journal}}: Check |doi= value (help); External link in |doi= (help)
  14. ^ Capelli, Florent; Strozecki, Yann (August 2018). "Incremental delay enumeration: Space and time". Discrete Applied Mathematics. doi:https://doi.org/10.1016/j.dam.2018.06.038. {{cite journal}}: Check |doi= value (help); External link in |doi= (help)
  15. ^ Eiter, Thomas; Gottlob, Georg (December 1995). "Identifying the Minimal Transversals of a Hypergraph and Related Problems". SIAM Journal on Computing. 24 (6): 1278–1304. doi:10.1137/S0097539793250299.
  16. ^ Kanté, Mamadou Moustapha; Limouzy, Vincent; Mary, Arnaud; Nourine, Lhouari (January 2014). "On the Enumeration of Minimal Dominating Sets and Related Notions". SIAM Journal on Discrete Mathematics. 28 (4): 1916–1929. doi:10.1137/120862612.
  17. ^ Fredman, Michael L.; Khachiyan, Leonid (November 1996). "On the Complexity of Dualization of Monotone Disjunctive Normal Forms". Journal of Algorithms. 21 (3): 618–628. doi:https://doi.org/10.1006/jagm.1996.0062. {{cite journal}}: Check |doi= value (help); External link in |doi= (help)
edit