wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

commit 2330b489eda432165b66f188f802ed419d9391cc
parent e1d2d4206c78089b0890e7984531b391c6c456bf
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 21 May 2025 19:46:44 +0200

commit with codex

Diffstat:
2horn_clause | 2++
boolean_formulas_positive | 2+-
deficiency | 4+++-
dynamic_membership_word | 2++
enumeration_ordered | 1+
graph_deficiency_weighted | 7+++++++
horn_2sat | 2+-
horn_cnf | 7+++++++
horn_sat | 2+-
monotone2cnf | 7+++++++
probabilities | 1+
project_selection_problem | 2++
12 files changed, 35 insertions(+), 4 deletions(-)

diff --git a/2horn_clause b/2horn_clause @@ -7,3 +7,5 @@ maybe should be "definite 2horn" Up: [horn_clause] See also: [2sat], [horn_2sat] + +Aliases: 2horn clauses diff --git a/boolean_formulas_positive b/boolean_formulas_positive @@ -4,4 +4,4 @@ A [Boolean_formula] which is [positive], i.e., does not use [negation] Up: [boolean_formula] -Aliases: positive Boolean formula, positive Boolean formulas +Aliases: positive Boolean formula, positive Boolean formulas, Boolean formula positive diff --git a/deficiency b/deficiency @@ -4,8 +4,10 @@ https://en.wikipedia.org/wiki/Deficiency_(graph_theory) on [graph] and [graph_bipartite] -weighted variant: https://cstheory.stackexchange.com/questions/54787/can-you-compute-in-ptime-a-weighted-version-of-deficiency-on-a-bipartite-graph/54788 +weighted variant: [graph_deficiency_weighted] Up: [graph] See also: [project_selection_problem], [matching] + +Aliases: graph deficiency diff --git a/dynamic_membership_word b/dynamic_membership_word @@ -12,3 +12,5 @@ Depends on which [updates_word] are allowed: - for [regular_expressions_counting]: [bjorklund2015succinct] Up: [dynamic_membership], [dynamic_word] + +Aliases: dynamic membership words diff --git a/enumeration_ordered b/enumeration_ordered @@ -3,6 +3,7 @@ - [enumeration_ordered_cq] - [enumeration_ordered_mso] - [enumeration_ordered_paths] +- [enumeration_ordered_boolean_function] Up: [enumeration], [order] diff --git a/graph_deficiency_weighted b/graph_deficiency_weighted @@ -0,0 +1,7 @@ +# Graph deficiency weighted + +https://cstheory.stackexchange.com/questions/54787/can-you-compute-in-ptime-a-weighted-version-of-deficiency-on-a-bipartite-graph/54788 + +connection to [project_selection_problem] + +Up: [deficiency] diff --git a/horn_2sat b/horn_2sat @@ -1,5 +1,5 @@ # Horn 2sat -[satisfiability_boolean] with [2horn_clause] +[satisfiability_boolean] for [2horn] [Boolean_formula] Up: [horn_sat], [2sat] diff --git a/horn_cnf b/horn_cnf @@ -0,0 +1,7 @@ +# Horn CNF + +A [conjunction] of [horn_clauses] + +Up: [horn_clause] + +See also: [horn_sat] diff --git a/horn_sat b/horn_sat @@ -2,7 +2,7 @@ https://en.wikipedia.org/wiki/Horn-satisfiability -[satisfiability_boolean] with [horn_clause] +[satisfiability_boolean] with [horn_CNF] In [ptime], and [p_complete] diff --git a/monotone2cnf b/monotone2cnf @@ -0,0 +1,7 @@ +# monotone2cnf + +A [monotone_CNF] which is a [2CNF] + +Up: [monotone_CNF], [2CNF] + +Aliases: monotone_2_CNF diff --git a/probabilities b/probabilities @@ -8,6 +8,7 @@ Tasks: - [probabilistic_inference] - [maximum_a_posteriori] - [marginal_computation] +- [most_probable_explanation] Algorithms: diff --git a/project_selection_problem b/project_selection_problem @@ -10,3 +10,5 @@ also works for arbitrary [directed_graphs] not just [bipartite_graphs] - cf https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Project_Selection.pdf Up: [network_flow] + +See also: [graph_deficiency_weighted]