commit d3cba66b4b4164ca3da9c0bb59b9d4a70a95d8e1
parent 0af1c2b02431e5643f82886538e4916dbb59432f
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 11 Apr 2025 18:53:49 +0200
commit with codex
Diffstat:
9 files changed, 27 insertions(+), 7 deletions(-)
diff --git a/3cnf b/3cnf
@@ -1,6 +1,6 @@
# 3CNF
-[conjunctive_normal_form] [boolean_formula] with 3 literals per clause
+[conjunctive_normal_form] [boolean_formula] with 3 literals per clause ([CNF_dimension] 3)
Up: [conjunctive_normal_form]
diff --git a/computational_problem b/computational_problem
@@ -7,6 +7,7 @@
- [approximation_problem]
- [counting_problem]
- [function_problem]
+- [enumeration_problem]
## Terminology
diff --git a/conjunctive_normal_form b/conjunctive_normal_form
@@ -13,10 +13,7 @@ Types:
lower bound on size of CNF relative to [disjunctive_normal_form]
-[variable_clause_difference]
-
Graphs:
-
- [primal_graph]
- [dual_graph]
- [incidence_graph]
@@ -26,11 +23,16 @@ Parameters:
- [primal_treewidth]
- [dual_treewidth]
- [incidence_treewidth]
+- [CNF_dimension]
+- [variable_clause_difference]
[conversion]:
- [cnf_to_dnnf]
- [cnf_to_decision_dnnf]
+Notions:
+- [Sub_CNF]: a [subset] of the [clauses]
+
See also: [disjunctive_normal_form], [dualization]
Up: [boolean_formula]
diff --git a/enumeration_definition b/enumeration_definition
@@ -4,4 +4,6 @@ An [enumeration_algorithm] consists of two phases:
- A [preprocessing_phase]
- An [enumeration_phase] where you measure [enumeration_delay]
+To solve an [enumeration_problem]
+
Up: [enumeration]
diff --git a/enumeration_delay b/enumeration_delay
@@ -1,13 +1,22 @@
# Enumeration delay
-The [worst_case] running time between the production of two consecutive results in an [enumeration_algorithm].
+The [worst_case] running time between the production of two consecutive results in an [enumeration_algorithm], or the time to decide that enumeration has concluded after the last solution
Possible types:
- [constant_delay]
-- [output_linear_delay]
+ - [linear_preprocessing_constant_delay]
- [polylog_delay]
+- [polynomial_delay]
+
+Variants:
+- [output_linear_delay]
+- [polynomial_total_time]
+- [incremental_polynomial_time]
+- notion de [incremental_total_time], cf
Up: [enumeration_definition]
See also: [access_time]
+
+Aliases: delay
diff --git a/horn_sat b/horn_sat
@@ -11,3 +11,5 @@ For [pqe]:
- even in the case of [horn_2sat]
Up: [sat_variants] with [horn_clause]
+
+See also: [horn_cnf]
diff --git a/independent_set b/independent_set
@@ -2,7 +2,7 @@
https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29
-An *independent set* is a [subset] of [vertices] of an [undirected_graph] such that no two [vertices] of the [subset] are [adjacent]. Also called a "coclique" or "anticlique".
+An *independent set* is a [subset] of [vertices] of an [undirected_graph] such that no two [vertices] of the [subset] are [adjacent]. Also called a "coclique" or "anticlique", or a "stable"
## Connections
@@ -15,6 +15,7 @@ An *independent set* is a [subset] of [vertices] of an [undirected_graph] such t
- [maximum_independent_set]: [np_hard] to find, mais [ptime] in [graph_bipartite] ([maximum_independent_set_bipartite])
- [maximal_independent_set]: [ptime] to find with [greedy_algorithm]
- [generalized_dominating_set]
+- [independent_set_enumeration]
## [counting]
diff --git a/order b/order
@@ -8,3 +8,5 @@
- [upper_bound] / [lower_bound]
Up: [mathematics]
+
+Aliases: order relation
diff --git a/partial_order b/partial_order
@@ -10,6 +10,7 @@ Variants:
- [crown] and link with [partial_order_dimension]
- [trotter1973dimension]
- [order_type]
+- [componentwise_order], cf [Pareto]
- [omega_complete]
- [ascending_chain_condition]
