wiki_research

commit 5eb21424dd64221a3e3de0228652e2f14ed3079f
parent d860d9f746d3fa40daf0c2a36158f51069b25b2d
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon,  6 Jan 2025 09:52:51 +0100

commit with codex

Diffstat:
boolean_formula
 | 
2
+-
equation
 | 
2
+-
function
 | 
2
++
literal
 | 
2
++
mathematics
 | 
5
+++++
positive_threshold_function
 | 
7
+++++++
representation
 | 
8
++++++++
spanning_tree
 | 
2
++
submodular_approximation
 | 
5
+++++
submodular_function
 | 
9
+++++++++
submodular_optimization
 | 
3
++-
submodular_set_function
 | 
2
+-
threshold
 | 
7
+++++++
tree_even
 | 
13
+++++++++++++
tree_odd
 | 
9
+++++++++

15 files changed, 74 insertions(+), 4 deletions(-)
diff --git a/boolean_formula b/boolean_formula
@@ -9,6 +9,6 @@ An [expression] which represents a [boolean_function], built from [literals] usi
 - [term]
 - [literal]
 
-Up: [boolean_function]
+Up: [representation] of [boolean_function]
 
 See also: [boolean_circuit], [knowledge_compilation_classes]
diff --git a/equation b/equation
@@ -9,4 +9,4 @@
 
 Up: [mathematics]
 
-See also: [disequation], [inequation]
+See also: [disequation], [inequation], [equality]
diff --git a/function b/function
@@ -21,3 +21,5 @@ Notions:
 Up: [mathematics]
 
 See also: [functional_dependency]
+
+Aliases: functions
diff --git a/literal b/literal
@@ -3,3 +3,5 @@
 Either a [variable] or the [negation] of a [variable]
 
 Up: [boolean_formula]
+
+Aliases: literals
diff --git a/mathematics b/mathematics
@@ -28,6 +28,8 @@
 - [function]
 - [equation]
   - [equation_system]
+  - [inequation]
+  - [disequation]
 - [sequence]
 - [cartesian_product]
 - [plane_mathematics]
@@ -44,6 +46,9 @@
 - [infinite]
 - [cardinal]
 - [fourier_transform]
+- [equality]
+- [inequality_mathematics]
+- [disequality]
 
 ## Fields
 
diff --git a/positive_threshold_function b/positive_threshold_function
@@ -0,0 +1,7 @@
+# Positive threshold function
+
+cf https://cstheory.stackexchange.com/questions/31469/which-monotone-boolean-functions-are-representable-as-thresholds-on-sums
+
+Up: [boolean_function_classes]
+
+See also: [threshold]
diff --git a/representation b/representation
@@ -0,0 +1,8 @@
+# Representation
+
+- of [boolean_function]
+  - [boolean_formula]
+  - [boolean_circuit]
+  - [pseudo_boolean_constraint]
+
+Up: [mathematics]
diff --git a/spanning_tree b/spanning_tree
@@ -6,3 +6,5 @@
 See also: [steiner_tree]
 
 Up: [tree]
+
+Aliases: spanning trees
diff --git a/submodular_approximation b/submodular_approximation
@@ -0,0 +1,5 @@
+# Submodular approximation
+
+[hochbaum2017submodular]
+
+Up: [submodular_optimization], [approximation]
diff --git a/submodular_function b/submodular_function
@@ -0,0 +1,9 @@
+# Submodular function
+
+- on [sets]: [submodular_set_function]
+- the [domain] may be different
+
+[zivny2009expressive]: [submodular_function_locally_defined], i.e., a [sum] of [functions] of bounded [arity]
+  - related to [pseudo_boolean_optimization]
+
+Up: [function]
diff --git a/submodular_optimization b/submodular_optimization
@@ -4,5 +4,6 @@ https://en.wikipedia.org/wiki/Submodular_set_function#Optimization_problems
 
 - [submodular_minimization]
 - [submodular_maximization]
+- [submodular_approximation]
 
-Up: [optimization]
+Up: [optimization], [submodular_function]
diff --git a/submodular_set_function b/submodular_set_function
@@ -9,4 +9,4 @@ Implies being [subadditive], converse is not true in general
 
 See also: [submodular_optimization], [concave_function]
 
-Up: [function]
+Up: [submodular_function]
diff --git a/threshold b/threshold
@@ -0,0 +1,7 @@
+# Threshold
+
+- [positive_threshold_function]
+- [pqe_threshold]
+- [locally_threshold_testable_language]
+
+Up: [mathematics]
diff --git a/tree_even b/tree_even
@@ -0,0 +1,13 @@
+# Tree even
+
+A [tree] where the length of the unique [path] connecting any two [leaves] is [even]
+
+[hanaka2024complexity] studies the problem of finding [spanning_trees] that are even.
+- [NP_hard] on general [undirected_graphs]
+- [PTIME] on [bipartite_graphs]
+
+Up: [tree]
+
+Aliases: even tree, even trees
+
+See also: [tree_odd]
diff --git a/tree_odd b/tree_odd
@@ -0,0 +1,9 @@
+# Tree odd
+
+A [tree] where the length of the unique [path] connecting any two [leaves] is [odd]
+
+[hanaka2024complexity] remarks it is equivalent to requiring that the tree is a [path]
+
+Up: [tree]
+
+See also: [tree_even]