Enumeration algorithm - Revision history

OAbot: Open access bot: arxiv updated in citation with #oabot.

2025-04-07T05:20:11Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 05:20, 7 April 2025
Line 13:		Line 13:
	Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class]]es have been introduced for such problems.		Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class]]es have been introduced for such problems.

	A very general such class is '''EnumP''',<ref name="closure">{{cite journal\|last1=Strozecki\|first1=Yann\|last2=Mary\|first2=Arnaud\|date=2019\|title=Efficient Enumeration of Solutions Produced by Closure Operations\|url=https://dmtcs.episciences.org/5549\|journal=Discrete Mathematics & Theoretical Computer Science\|volume=21\|issue=3\|doi=10.23638/DMTCS-21-3-22}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP''',<ref name="closure">{{cite journal\|last1=Strozecki\|first1=Yann\|last2=Mary\|first2=Arnaud\|date=2019\|title=Efficient Enumeration of Solutions Produced by Closure Operations\|url=https://dmtcs.episciences.org/5549\|journal=Discrete Mathematics & Theoretical Computer Science\|volume=21\|issue=3\|doi=10.23638/DMTCS-21-3-22\|arxiv=1712.03714}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific:		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific:

Citation bot: Alter: pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 1054/2500

2023-01-03T21:28:48Z

Alter: pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 1054/2500

← Previous revision		Revision as of 21:28, 3 January 2023
Line 25:		Line 25:
	== Common techniques ==		== Common techniques ==

	* '''[[Backtracking]]''': The simplest way to enumerate all solutions is by systematically exploring the space of possible results ([[partition (mathematics)\|partitioning]] it at each successive step).<ref>{{cite journal\|last1=Read\|first1=Ronald C.\|author-link1=Ronald C. Read\|last2=Tarjan\|first2=Robert E.\|author-link2=Robert Tarjan\|date=1975\|title=Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees\|url=https://onlinelibrary.wiley.com/doi/10.1002/net.1975.5.3.237\|journal=Networks\|volume=5\|issue=3\|pages=~~237-252~~\|doi=10.1002/net.1975.5.3.237}}</ref> However, performing this may not give good guarantees on the delay, i.e., a backtracking algorithm may spend a long time exploring parts of the space of possible results that do not give rise to a full solution.		* '''[[Backtracking]]''': The simplest way to enumerate all solutions is by systematically exploring the space of possible results ([[partition (mathematics)\|partitioning]] it at each successive step).<ref>{{cite journal\|last1=Read\|first1=Ronald C.\|author-link1=Ronald C. Read\|last2=Tarjan\|first2=Robert E.\|author-link2=Robert Tarjan\|date=1975\|title=Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees\|url=https://onlinelibrary.wiley.com/doi/10.1002/net.1975.5.3.237\|journal=Networks\|volume=5\|issue=3\|pages=237–252\|doi=10.1002/net.1975.5.3.237}}</ref> However, performing this may not give good guarantees on the delay, i.e., a backtracking algorithm may spend a long time exploring parts of the space of possible results that do not give rise to a full solution.
	* '''{{visible anchor\|Flashlight search}}''': This technique improves on backtracking by exploring the space of all possible solutions but solving at each step the problem of whether the current partial solution can be extended to a partial solution.<ref name="closure"/> If the answer is no, then the algorithm can immediately backtrack and avoid wasting time, which makes it easier to show guarantees on the delay between any two complete solutions. In particular, this technique applies well to [[self-reducible]] problems.		* '''{{visible anchor\|Flashlight search}}''': This technique improves on backtracking by exploring the space of all possible solutions but solving at each step the problem of whether the current partial solution can be extended to a partial solution.<ref name="closure"/> If the answer is no, then the algorithm can immediately backtrack and avoid wasting time, which makes it easier to show guarantees on the delay between any two complete solutions. In particular, this technique applies well to [[self-reducible]] problems.
	* '''Closure under set operations''': If we wish to enumerate the disjoint [[union (set theory)\|union]] of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in [[sorting\|sorted order]], then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a [[hash table]]. Likewise, the [[cartesian product]] of two sets can be enumerated efficiently by enumerating one set and joining each result with all results obtained when enumerating the second step.		* '''Closure under set operations''': If we wish to enumerate the disjoint [[union (set theory)\|union]] of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in [[sorting\|sorted order]], then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a [[hash table]]. Likewise, the [[cartesian product]] of two sets can be enumerated efficiently by enumerating one set and joining each result with all results obtained when enumerating the second step.

A3nm: /* Common complexity classes */ typo

2022-11-13T09:46:20Z

Common complexity classes: typo

← Previous revision		Revision as of 09:46, 13 November 2022
Line 15:		Line 15:
	A very general such class is '''EnumP''',<ref name="closure">{{cite journal\|last1=Strozecki\|first1=Yann\|last2=Mary\|first2=Arnaud\|date=2019\|title=Efficient Enumeration of Solutions Produced by Closure Operations\|url=https://dmtcs.episciences.org/5549\|journal=Discrete Mathematics & Theoretical Computer Science\|volume=21\|issue=3\|doi=10.23638/DMTCS-21-3-22}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP''',<ref name="closure">{{cite journal\|last1=Strozecki\|first1=Yann\|last2=Mary\|first2=Arnaud\|date=2019\|title=Efficient Enumeration of Solutions Produced by Closure Operations\|url=https://dmtcs.episciences.org/5549\|journal=Discrete Mathematics & Theoretical Computer Science\|volume=21\|issue=3\|doi=10.23638/DMTCS-21-3-22}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific:

	* '''Output polynomial''', the class of problems whose complete output can be computed in polynomial time.		* '''Output polynomial''', the class of problems whose complete output can be computed in polynomial time.

2A02:8109:B03F:F738:91C8:3EC6:961C:2290: references

2022-05-29T12:13:17Z

references

Citation bot: Alter: template type. Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 885/1776

2022-01-29T21:03:44Z

Alter: template type. Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 885/1776

← Previous revision		Revision as of 21:03, 29 January 2022
Line 13:		Line 13:
	Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class]]es have been introduced for such problems.		Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class]]es have been introduced for such problems.

	A very general such class is '''EnumP''',<ref>{{Cite ~~arxiv~~\|~~last~~=Strozecki\|~~first~~=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|language=en\|eprint=1509.05623\|class=cs.CC}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP''',<ref>{{Cite arXiv\|last1=Strozecki\|first1=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|language=en\|eprint=1509.05623\|class=cs.CC}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific
Line 33:		Line 33:
	* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.		* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.
	* Enumerating the [[minimal transversal]]s of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{Cite web\|url=https://cuvillier.de/de/shop/publications/1237\|title="Algorithmic and Computational Complexity Issues of MONET – Cuvillier Verlag\|website=cuvillier.de\|access-date=2019-05-23}}</ref>		* Enumerating the [[minimal transversal]]s of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{Cite web\|url=https://cuvillier.de/de/shop/publications/1237\|title="Algorithmic and Computational Complexity Issues of MONET – Cuvillier Verlag\|website=cuvillier.de\|access-date=2019-05-23}}</ref>
	* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|~~last~~=Bagan\|~~first~~=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration\|journal=Computer Science Logic\|volume=4646\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>		* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last1=Bagan\|first1=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration\|journal=Computer Science Logic\|volume=4646\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>
	* The problem of [[Clique problem#Listing all maximal cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]		* The problem of [[Clique problem#Listing all maximal cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]
	* Listing all elements of structures such as [[matroid]]s and [[greedoid]]s		* Listing all elements of structures such as [[matroid]]s and [[greedoid]]s
	* Several problems on graphs, e.g., enumerating [[independent set (graph theory)\|independent set]]s, [[path (graph theory)\|paths]], [[cut (graph theory)\|cuts]], etc.		* Several problems on graphs, e.g., enumerating [[independent set (graph theory)\|independent set]]s, [[path (graph theory)\|paths]], [[cut (graph theory)\|cuts]], etc.
	* Enumerating the [[Boolean satisfiability problem\|satisfying assignment]]s of representations of [[Boolean function]]s, e.g., a Boolean formula written in [[conjunctive normal form]] or [[disjunctive normal form]], a [[binary decision diagram]] such as an [[OBDD]], or a [[Boolean circuit]] in restricted classes studied in [[knowledge compilation]], e.g., [[Negation normal form\|NNF]].<ref>{{Cite journal\|~~last~~=Marquis\|~~first~~=P.\|last2=Darwiche\|first2=A.\|date=2002\|title=A Knowledge Compilation Map\|journal=Journal of Artificial Intelligence Research\|volume=17\|pages=229–264\|language=en\|doi=10.1613/jair.989\|arxiv=1106.1819}}</ref>		* Enumerating the [[Boolean satisfiability problem\|satisfying assignment]]s of representations of [[Boolean function]]s, e.g., a Boolean formula written in [[conjunctive normal form]] or [[disjunctive normal form]], a [[binary decision diagram]] such as an [[OBDD]], or a [[Boolean circuit]] in restricted classes studied in [[knowledge compilation]], e.g., [[Negation normal form\|NNF]].<ref>{{Cite journal\|last1=Marquis\|first1=P.\|last2=Darwiche\|first2=A.\|date=2002\|title=A Knowledge Compilation Map\|journal=Journal of Artificial Intelligence Research\|volume=17\|pages=229–264\|language=en\|doi=10.1613/jair.989\|arxiv=1106.1819\|s2cid=9919794}}</ref>

	== Connection to computability theory ==		== Connection to computability theory ==

Headbomb: Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published)

2020-10-16T18:15:41Z

Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published)

Headbomb: Add: class, eprint. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this tool yourself. Report bugs here. | via #UCB_Gadget

2020-01-29T00:52:45Z

Add: class, eprint. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this tool yourself. Report bugs here. | via #UCB_Gadget

← Previous revision		Revision as of 00:52, 29 January 2020
Line 13:		Line 13:
	Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class\|complexity classes]] have been introduced for such problems.		Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class\|complexity classes]] have been introduced for such problems.

	A very general such class is '''EnumP'''<ref>{{Cite ~~journal~~\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|language=en\|~~arxiv~~=1509.05623\|~~bibcode~~=~~2015arXiv150905623M~~}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP'''<ref>{{Cite arxiv\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|language=en\|eprint=1509.05623\|class=cs.CC}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific

Headbomb: Alter: journal. Add: arxiv, pages, volume, bibcode. Removed URL that duplicated unique identifier. Formatted dashes. | You can use this tool yourself. Report bugs here. | via #UCB_Gadget

2020-01-29T00:51:35Z

Alter: journal. Add: arxiv, pages, volume, bibcode. Removed URL that duplicated unique identifier. Formatted dashes. | You can use this tool yourself. Report bugs here. | via #UCB_Gadget

← Previous revision		Revision as of 00:51, 29 January 2020
Line 13:		Line 13:
	Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class\|complexity classes]] have been introduced for such problems.		Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class\|complexity classes]] have been introduced for such problems.

	A very general such class is '''EnumP'''<ref>{{Cite journal\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations~~\|url=https://arxiv.org/abs/1712.03714v3~~\|language=en\|arxiv=1509.05623}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP'''<ref>{{Cite journal\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|language=en\|arxiv=1509.05623\|bibcode=2015arXiv150905623M}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific
Line 33:		Line 33:
	* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.		* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.
	* Enumerating the [[minimal transversal\|minimal transversals]] of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{Cite web\|url=https://cuvillier.de/de/shop/publications/1237\|title="Algorithmic and Computational Complexity Issues of MONET – Cuvillier Verlag\|website=cuvillier.de\|access-date=2019-05-23}}</ref>		* Enumerating the [[minimal transversal\|minimal transversals]] of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{Cite web\|url=https://cuvillier.de/de/shop/publications/1237\|title="Algorithmic and Computational Complexity Issues of MONET – Cuvillier Verlag\|website=cuvillier.de\|access-date=2019-05-23}}</ref>
	* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last=Bagan\|first=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration~~\|url=https://link.springer.com/chapter/10.1007/978-3-540-74915-8_18~~\|journal=Computer Science Logic\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>		* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last=Bagan\|first=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration\|journal=Computer Science Logic\|volume=4646\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>
	* The problem of [[Clique_problem#Listing_all_maximal_cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]		* The problem of [[Clique_problem#Listing_all_maximal_cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]
	* Listing all elements of structures such as [[matroid]]s and [[greedoid]]s		* Listing all elements of structures such as [[matroid]]s and [[greedoid]]s
	* Several problems on graphs, e.g., enumerating [[independent set (graph theory)\|independent set]]s, [[path (graph theory)\|paths]], [[cut (graph theory)\|cuts]], etc.		* Several problems on graphs, e.g., enumerating [[independent set (graph theory)\|independent set]]s, [[path (graph theory)\|paths]], [[cut (graph theory)\|cuts]], etc.
	* Enumerating the [[Boolean satisfiability problem\|satisfying assignment]]s of representations of [[Boolean function]]s, e.g., a Boolean formula written in [[conjunctive normal form]] or [[disjunctive normal form]], a [[binary decision diagram]] such as an [[OBDD]], or a [[Boolean circuit]] in restricted classes studied in [[knowledge compilation]], e.g., [[Negation normal form\|NNF]].<ref>{{Cite journal\|last=Marquis\|first=P.\|last2=Darwiche\|first2=A.\|date=2002\|title=A Knowledge Compilation Map~~\|url=https://arxiv.org/abs/1106.1819v1~~\|journal=Journal Of Artificial Intelligence Research\|language=en\|doi=10.1613/jair.989}}</ref>		* Enumerating the [[Boolean satisfiability problem\|satisfying assignment]]s of representations of [[Boolean function]]s, e.g., a Boolean formula written in [[conjunctive normal form]] or [[disjunctive normal form]], a [[binary decision diagram]] such as an [[OBDD]], or a [[Boolean circuit]] in restricted classes studied in [[knowledge compilation]], e.g., [[Negation normal form\|NNF]].<ref>{{Cite journal\|last=Marquis\|first=P.\|last2=Darwiche\|first2=A.\|date=2002\|title=A Knowledge Compilation Map\|journal=Journal of Artificial Intelligence Research\|volume=17\|pages=229–264\|language=en\|doi=10.1613/jair.989\|arxiv=1106.1819v1}}</ref>

	== Connection to computability theory ==		== Connection to computability theory ==

Jarble: adding a section anchor

2020-01-16T20:47:41Z

adding a section anchor

← Previous revision		Revision as of 20:47, 16 January 2020
Line 26:		Line 26:

	* '''[[Backtracking]]''': The simplest way to enumerate all solutions is by systematically exploring the space of possible results ([[partition (mathematics)\|partitioning]] it at each successive step). However, performing this may not give good guarantees on the delay, i.e., a backtracking algorithm may spend a long time exploring parts of the space of possible results that do not give rise to a full solution.		* '''[[Backtracking]]''': The simplest way to enumerate all solutions is by systematically exploring the space of possible results ([[partition (mathematics)\|partitioning]] it at each successive step). However, performing this may not give good guarantees on the delay, i.e., a backtracking algorithm may spend a long time exploring parts of the space of possible results that do not give rise to a full solution.
	* '''Flashlight search''': This technique improves on backtracking by exploring the space of all possible solutions but solving at each step the problem of whether the current partial solution can be extended to a partial solution. If the answer is no, then the algorithm can immediately backtrack and avoid wasting time, which makes it easier to show guarantees on the delay between any two complete solutions. In particular, this technique applies well to [[self-reducible]] problems.		* '''{{visible anchor\|Flashlight search}}''': This technique improves on backtracking by exploring the space of all possible solutions but solving at each step the problem of whether the current partial solution can be extended to a partial solution. If the answer is no, then the algorithm can immediately backtrack and avoid wasting time, which makes it easier to show guarantees on the delay between any two complete solutions. In particular, this technique applies well to [[self-reducible]] problems.
	* '''Closure under set operations''': If we wish to enumerate the disjoint [[union (set theory)\|union]] of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in [[sorting\|sorted order]], then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a [[hash table]]. Likewise, the [[cartesian product]] of two sets can be enumerated efficiently by enumerating one set and joining each result with all results obtained when enumerating the second step.		* '''Closure under set operations''': If we wish to enumerate the disjoint [[union (set theory)\|union]] of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in [[sorting\|sorted order]], then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a [[hash table]]. Likewise, the [[cartesian product]] of two sets can be enumerated efficiently by enumerating one set and joining each result with all results obtained when enumerating the second step.

OAbot: Open access bot: add arxiv identifier to citation with #oabot.

2019-07-25T14:25:00Z

Open access bot: add arxiv identifier to citation with #oabot.

← Previous revision		Revision as of 14:25, 25 July 2019
Line 13:		Line 13:
	Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class\|complexity classes]] have been introduced for such problems.		Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class\|complexity classes]] have been introduced for such problems.

	A very general such class is '''EnumP'''<ref>{{Cite journal\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|url=https://arxiv.org/abs/1712.03714v3\|language=en}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP'''<ref>{{Cite journal\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|url=https://arxiv.org/abs/1712.03714v3\|language=en\|arxiv=1509.05623}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific

← Previous revision		Revision as of 00:51, 29 January 2020
Line 13:		Line 13:
	Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class\|complexity classes]] have been introduced for such problems.		Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class\|complexity classes]] have been introduced for such problems.

	A very general such class is '''EnumP'''<ref>{{Cite journal\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations~~\|url=https://arxiv.org/abs/1712.03714v3~~\|language=en\|arxiv=1509.05623}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP'''<ref>{{Cite journal\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|language=en\|arxiv=1509.05623\|bibcode=2015arXiv150905623M}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific
Line 33:		Line 33:
	* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.		* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.
	* Enumerating the [[minimal transversal\|minimal transversals]] of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{Cite web\|url=https://cuvillier.de/de/shop/publications/1237\|title="Algorithmic and Computational Complexity Issues of MONET – Cuvillier Verlag\|website=cuvillier.de\|access-date=2019-05-23}}</ref>		* Enumerating the [[minimal transversal\|minimal transversals]] of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{Cite web\|url=https://cuvillier.de/de/shop/publications/1237\|title="Algorithmic and Computational Complexity Issues of MONET – Cuvillier Verlag\|website=cuvillier.de\|access-date=2019-05-23}}</ref>
	* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last=Bagan\|first=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration~~\|url=https://link.springer.com/chapter/10.1007/978-3-540-74915-8_18~~\|journal=Computer Science Logic\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>		* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last=Bagan\|first=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration\|journal=Computer Science Logic\|volume=4646\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>
	* The problem of [[Clique_problem#Listing_all_maximal_cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]		* The problem of [[Clique_problem#Listing_all_maximal_cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]
	* Listing all elements of structures such as [[matroid]]s and [[greedoid]]s		* Listing all elements of structures such as [[matroid]]s and [[greedoid]]s
	* Several problems on graphs, e.g., enumerating [[independent set (graph theory)\|independent set]]s, [[path (graph theory)\|paths]], [[cut (graph theory)\|cuts]], etc.		* Several problems on graphs, e.g., enumerating [[independent set (graph theory)\|independent set]]s, [[path (graph theory)\|paths]], [[cut (graph theory)\|cuts]], etc.
	* Enumerating the [[Boolean satisfiability problem\|satisfying assignment]]s of representations of [[Boolean function]]s, e.g., a Boolean formula written in [[conjunctive normal form]] or [[disjunctive normal form]], a [[binary decision diagram]] such as an [[OBDD]], or a [[Boolean circuit]] in restricted classes studied in [[knowledge compilation]], e.g., [[Negation normal form\|NNF]].<ref>{{Cite journal\|last=Marquis\|first=P.\|last2=Darwiche\|first2=A.\|date=2002\|title=A Knowledge Compilation Map~~\|url=https://arxiv.org/abs/1106.1819v1~~\|journal=Journal Of Artificial Intelligence Research\|language=en\|doi=10.1613/jair.989}}</ref>		* Enumerating the [[Boolean satisfiability problem\|satisfying assignment]]s of representations of [[Boolean function]]s, e.g., a Boolean formula written in [[conjunctive normal form]] or [[disjunctive normal form]], a [[binary decision diagram]] such as an [[OBDD]], or a [[Boolean circuit]] in restricted classes studied in [[knowledge compilation]], e.g., [[Negation normal form\|NNF]].<ref>{{Cite journal\|last=Marquis\|first=P.\|last2=Darwiche\|first2=A.\|date=2002\|title=A Knowledge Compilation Map\|journal=Journal of Artificial Intelligence Research\|volume=17\|pages=229–264\|language=en\|doi=10.1613/jair.989\|arxiv=1106.1819v1}}</ref>

	== Connection to computability theory ==		== Connection to computability theory ==

← Previous revision		Revision as of 12:13, 29 May 2022
Line 13:		Line 13:
	Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class]]es have been introduced for such problems.		Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class]]es have been introduced for such problems.

	A very general such class is '''EnumP''',<ref>{{~~Cite~~ ~~arXiv~~\|last1=Strozecki\|first1=Yann\|last2=Mary\|first2=Arnaud\|date=~~2017-12-11~~\|title=Efficient ~~enumeration~~ of ~~solutions~~ ~~produced~~ by ~~closure~~ ~~operations~~\|~~language~~=en\|~~eprint~~=~~1509.05623~~\|~~class~~=cs.CC}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP''',<ref name="closure">{{cite journal\|last1=Strozecki\|first1=Yann\|last2=Mary\|first2=Arnaud\|date=2019\|title=Efficient Enumeration of Solutions Produced by Closure Operations\|url=https://dmtcs.episciences.org/5549\|journal=Discrete Mathematics & Theoretical Computer Science\|volume=21\|issue=3\|doi=10.23638/DMTCS-21-3-22}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific
Line 25:		Line 25:
	== Common techniques ==		== Common techniques ==

	* '''[[Backtracking]]''': The simplest way to enumerate all solutions is by systematically exploring the space of possible results ([[partition (mathematics)\|partitioning]] it at each successive step). However, performing this may not give good guarantees on the delay, i.e., a backtracking algorithm may spend a long time exploring parts of the space of possible results that do not give rise to a full solution.		* '''[[Backtracking]]''': The simplest way to enumerate all solutions is by systematically exploring the space of possible results ([[partition (mathematics)\|partitioning]] it at each successive step).<ref>{{cite journal\|last1=Read\|first1=Ronald C.\|author-link1=Ronald C. Read\|last2=Tarjan\|first2=Robert E.\|author-link2=Robert Tarjan\|date=1975\|title=Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees\|url=https://onlinelibrary.wiley.com/doi/10.1002/net.1975.5.3.237\|journal=Networks\|volume=5\|issue=3\|pages=237-252\|doi=10.1002/net.1975.5.3.237}}</ref> However, performing this may not give good guarantees on the delay, i.e., a backtracking algorithm may spend a long time exploring parts of the space of possible results that do not give rise to a full solution.
	* '''{{visible anchor\|Flashlight search}}''': This technique improves on backtracking by exploring the space of all possible solutions but solving at each step the problem of whether the current partial solution can be extended to a partial solution. If the answer is no, then the algorithm can immediately backtrack and avoid wasting time, which makes it easier to show guarantees on the delay between any two complete solutions. In particular, this technique applies well to [[self-reducible]] problems.		* '''{{visible anchor\|Flashlight search}}''': This technique improves on backtracking by exploring the space of all possible solutions but solving at each step the problem of whether the current partial solution can be extended to a partial solution.<ref name="closure"/> If the answer is no, then the algorithm can immediately backtrack and avoid wasting time, which makes it easier to show guarantees on the delay between any two complete solutions. In particular, this technique applies well to [[self-reducible]] problems.
	* '''Closure under set operations''': If we wish to enumerate the disjoint [[union (set theory)\|union]] of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in [[sorting\|sorted order]], then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a [[hash table]]. Likewise, the [[cartesian product]] of two sets can be enumerated efficiently by enumerating one set and joining each result with all results obtained when enumerating the second step.		* '''Closure under set operations''': If we wish to enumerate the disjoint [[union (set theory)\|union]] of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in [[sorting\|sorted order]], then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a [[hash table]]. Likewise, the [[cartesian product]] of two sets can be enumerated efficiently by enumerating one set and joining each result with all results obtained when enumerating the second step.

Line 32:		Line 32:

	* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.		* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.
	* Enumerating the [[minimal transversal]]s of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{~~Cite~~ ~~web~~\|~~url~~=~~https://cuvillier.de/de/shop/publications/1237~~\|title=~~"~~Algorithmic and Computational Complexity Issues of MONET ~~– Cuvillier Verlag~~\|~~website~~=cuvillier.de\|~~access-date~~=~~2019-05-23~~}}</ref>		* Enumerating the [[minimal transversal]]s of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{cite book\|last=Hagen\|first=Matthias\|date=2008\|title=Algorithmic and Computational Complexity Issues of MONET\|url=https://cuvillier.de/de/shop/publications/1237\|location=Göttingen\|publisher=Cuvillier\|isbn=9783736928268}}</ref>
	* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last1=Bagan\|first1=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration\|journal=Computer Science Logic\|volume=4646\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>		* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last1=Bagan\|first1=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration\|journal=Computer Science Logic\|volume=4646\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>
	* The problem of [[Clique problem#Listing all maximal cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]		* The problem of [[Clique problem#Listing all maximal cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]

← Previous revision		Revision as of 18:15, 16 October 2020
Line 1:		Line 1:
	In [[computer science]], an '''enumeration algorithm''' is an [[algorithm]] that [[enumeration\|enumerates]] the answers to a [[computational problem]]. Formally, such an algorithm applies to problems that take an input and produce a list of solutions, similarly to [[function problems]]. For each input, the enumeration algorithm must produce the list of all solutions, without duplicates, and then halt. The performance of an enumeration algorithm is measured in terms of the time required to produce the solutions, either in terms of the '''total time''' required to produce all solutions, or in terms of the maximal '''delay''' between two consecutive solutions and in terms of a '''preprocessing''' time, counted as the time before outputting the first solution. This complexity can be expressed in terms of the size of the input, the size of each individual output, or the total size of the set of all outputs, similarly to what is done with [[output-sensitive algorithm~~\|output-sensitive algorithms~~]].		In [[computer science]], an '''enumeration algorithm''' is an [[algorithm]] that [[enumeration\|enumerates]] the answers to a [[computational problem]]. Formally, such an algorithm applies to problems that take an input and produce a list of solutions, similarly to [[function problems]]. For each input, the enumeration algorithm must produce the list of all solutions, without duplicates, and then halt. The performance of an enumeration algorithm is measured in terms of the time required to produce the solutions, either in terms of the '''total time''' required to produce all solutions, or in terms of the maximal '''delay''' between two consecutive solutions and in terms of a '''preprocessing''' time, counted as the time before outputting the first solution. This complexity can be expressed in terms of the size of the input, the size of each individual output, or the total size of the set of all outputs, similarly to what is done with [[output-sensitive algorithm]]s.

	== Formal definitions ==		== Formal definitions ==
Line 11:		Line 11:
	== Common complexity classes ==		== Common complexity classes ==

	Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class~~\|complexity classes~~]] have been introduced for such problems.		Enumeration problems have been studied in the context of [[computational complexity theory]], and several [[complexity class]]es have been introduced for such problems.

	A very general such class is '''EnumP'''<ref>{{Cite arxiv\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|language=en\|eprint=1509.05623\|class=cs.CC}}</ref>, the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].		A very general such class is '''EnumP''',<ref>{{Cite arxiv\|last=Strozecki\|first=Yann\|last2=Mary\|first2=Arnaud\|date=2017-12-11\|title=Efficient enumeration of solutions produced by closure operations\|language=en\|eprint=1509.05623\|class=cs.CC}}</ref> the class of problems for which the correctness of a possible output can be checked in [[polynomial time]] in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input ''x'', the candidate output ''y'', and solves the [[decision problem]] of whether ''y'' is a correct output for the input ''x'', in polynomial time in ''x'' and ''y''. For instance, this class contains all problems that amount to enumerating the [[witness (mathematics)\|witnesses]] of a problem in the [[class (complexity theory)\|class]] [[NP (complexity)\|NP]].

	Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific		Other classes that have been defined include the following. In the case of problems that are also in '''EnumP''', these problems are ordered from least to most specific
Line 32:		Line 32:

	* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.		* The [[vertex enumeration problem]], where we are given a [[polytope]] described as a [[system of equations\|system]] of [[linear inequality\|linear inequalities]] and we must enumerate the [[Vertex (geometry)\|vertices]] of the polytope.
	* Enumerating the [[minimal transversal~~\|minimal transversals~~]] of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{Cite web\|url=https://cuvillier.de/de/shop/publications/1237\|title="Algorithmic and Computational Complexity Issues of MONET – Cuvillier Verlag\|website=cuvillier.de\|access-date=2019-05-23}}</ref>		* Enumerating the [[minimal transversal]]s of a [[hypergraph (mathematics)\|hypergraph]]. This problem is related to [[monotone dualization]] and is connected to many applications in [[database theory]] and [[graph theory]].<ref>{{Cite web\|url=https://cuvillier.de/de/shop/publications/1237\|title="Algorithmic and Computational Complexity Issues of MONET – Cuvillier Verlag\|website=cuvillier.de\|access-date=2019-05-23}}</ref>
	* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last=Bagan\|first=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration\|journal=Computer Science Logic\|volume=4646\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>		* Enumerating the answers to a [[database query]], for instance a [[conjunctive query]] or a query expressed in [[monadic second-order]]. There have been characterizations in [[database theory]] of which conjunctive queries could be enumerated with [[linear time\|linear]] preprocessing and [[constant time\|constant]] delay.<ref>{{Cite journal\|last=Bagan\|first=Guillaume\|last2=Durand\|first2=Arnaud\|last3=Grandjean\|first3=Etienne\|date=2007\|editor-last=Duparc\|editor-first=Jacques\|editor2-last=Henzinger\|editor2-first=Thomas A.\|title=On Acyclic Conjunctive Queries and Constant Delay Enumeration\|journal=Computer Science Logic\|volume=4646\|series=Lecture Notes in Computer Science\|language=en\|publisher=Springer Berlin Heidelberg\|pages=208–222\|doi=10.1007/978-3-540-74915-8_18\|isbn=9783540749158}}</ref>
	* The problem of [[~~Clique_problem~~#~~Listing_all_maximal_cliques~~\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]		* The problem of [[Clique problem#Listing all maximal cliques\|enumerating maximal cliques]] in an input graph, e.g., with the [[Bron–Kerbosch algorithm]]
	* Listing all elements of structures such as [[matroid]]s and [[greedoid]]s		* Listing all elements of structures such as [[matroid]]s and [[greedoid]]s
	* Several problems on graphs, e.g., enumerating [[independent set (graph theory)\|independent set]]s, [[path (graph theory)\|paths]], [[cut (graph theory)\|cuts]], etc.		* Several problems on graphs, e.g., enumerating [[independent set (graph theory)\|independent set]]s, [[path (graph theory)\|paths]], [[cut (graph theory)\|cuts]], etc.
	* Enumerating the [[Boolean satisfiability problem\|satisfying assignment]]s of representations of [[Boolean function]]s, e.g., a Boolean formula written in [[conjunctive normal form]] or [[disjunctive normal form]], a [[binary decision diagram]] such as an [[OBDD]], or a [[Boolean circuit]] in restricted classes studied in [[knowledge compilation]], e.g., [[Negation normal form\|NNF]].<ref>{{Cite journal\|last=Marquis\|first=P.\|last2=Darwiche\|first2=A.\|date=2002\|title=A Knowledge Compilation Map\|journal=Journal of Artificial Intelligence Research\|volume=17\|pages=229–264\|language=en\|doi=10.1613/jair.989\|arxiv=1106.~~1819v1~~}}</ref>		* Enumerating the [[Boolean satisfiability problem\|satisfying assignment]]s of representations of [[Boolean function]]s, e.g., a Boolean formula written in [[conjunctive normal form]] or [[disjunctive normal form]], a [[binary decision diagram]] such as an [[OBDD]], or a [[Boolean circuit]] in restricted classes studied in [[knowledge compilation]], e.g., [[Negation normal form\|NNF]].<ref>{{Cite journal\|last=Marquis\|first=P.\|last2=Darwiche\|first2=A.\|date=2002\|title=A Knowledge Compilation Map\|journal=Journal of Artificial Intelligence Research\|volume=17\|pages=229–264\|language=en\|doi=10.1613/jair.989\|arxiv=1106.1819}}</ref>

	== Connection to computability theory ==		== Connection to computability theory ==