wiki_research

commit 74a1bfc06c2365cb44bb6f3036949aff54b95c65
parent ab98976126b8ac608c3b1cfe7047102551b2557b
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 10 Jun 2025 15:09:40 +0200

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
boolean_hierarchy
 | 
2
+-
certification_width
 | 
5
+++++
circuit
 | 
5
+++++
circuit_positive
 | 
9
+++++++++
circuit_trace
 | 
5
+++++
conjunction
 | 
2
++
degree
 | 
2
+-
disjunction
 | 
2
++
red_black_tree
 | 
5
+++++
sleep_sort
 | 
5
+++++
sorting
 | 
9
++-------
tree_balanced
 | 
7
+++++++
weighted_monotone_circuit_satisfiability
 | 
7
+++++++

13 files changed, 56 insertions(+), 9 deletions(-)
diff --git a/boolean_hierarchy b/boolean_hierarchy
@@ -7,4 +7,4 @@ https://complexityzoo.net/Complexity_Zoo:B#bh
 
 Up: [complexity_hierarchy]
 
-See also: [polynomial_hierarchy]
+See also: [polynomial_hierarchy], [QBF]
diff --git a/certification_width b/certification_width
@@ -0,0 +1,5 @@
+# Certification width
+
+defined in [rodriguesalves2021succinct], minimum size of a [circuit_trace] for a [positive_circuit]
+
+Up: [circuit]
diff --git a/circuit b/circuit
@@ -22,12 +22,17 @@
 - [enumeration_circuit]
 - [satisfiability]
 
+## Notions
+
+- [circuit_trace]
+
 ## Measure [circuit_parameter]
 
 - [depth]
 - [circuit_size]
 - [weft]
 - [fan_in]
+- [certification_width]
 
 ## Conditions
 
diff --git a/circuit_positive b/circuit_positive
@@ -0,0 +1,9 @@
+# Circuit positive
+
+A [circuit] without [negation] gates, i.e., with [variable] gates, [AND] gates, and [OR] gates
+
+Up: [circuit]
+
+Aliases: positive circuit, positive circuits
+
+See also: [circuit_monotone], [positive]
diff --git a/circuit_trace b/circuit_trace
@@ -0,0 +1,5 @@
+# Circuit trace
+
+cf [rodriguesalves2021succinct], which studies [succinct_monotone_circuit_certification] problem
+
+Up: [circuit]
diff --git a/conjunction b/conjunction
@@ -7,3 +7,5 @@
 Up: [boolean_operator]
 
 See also: [disjunction], [intersection]
+
+Aliases: AND
diff --git a/degree b/degree
@@ -9,4 +9,4 @@ In [directed_graphs], we can distinguish the [indegree] and [outdegree], respect
 
 Up: [graph_basic_notions]
 
-See also: [bounded_degree]
+See also: [bounded_degree_graphs]
diff --git a/disjunction b/disjunction
@@ -7,3 +7,5 @@
 Up: [boolean_operator]
 
 See also: [union], [conjunction]
+
+Aliases: OR
diff --git a/red_black_tree b/red_black_tree
@@ -0,0 +1,5 @@
+# Red black tree
+
+[purely_functional]: https://matt.might.net/articles/red-black-delete/
+
+Up: [tree_balanced]
diff --git a/sleep_sort b/sleep_sort
@@ -0,0 +1,5 @@
+# Sleep sort
+
+https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
+
+Up: [sorting]
diff --git a/sorting b/sorting
@@ -1,14 +1,9 @@
 # Sorting
 
-- [insertion_sort]
-- [selection_sort]
-- [heap_sort]
-- [binary_tree_sort]
-- [quicksort]
-- [merge_sort]
+- [comparison_sort]
+- [sleep_sort]
 - [bucket_sort]
 - [sorting_ram] on the [ram_model]
-- [bubble_sort]
 
 Up: [algorithms]
 
diff --git a/tree_balanced b/tree_balanced
@@ -0,0 +1,7 @@
+# Tree balanced
+
+- [tree_balanced_definitions]
+- [avl_tree]
+- [red_black_tree]
+
+Up: [tree]
diff --git a/weighted_monotone_circuit_satisfiability b/weighted_monotone_circuit_satisfiability
@@ -0,0 +1,7 @@
+# Weighted monotone circuit satisfiability (WMCS)
+
+studied in [rodriguesalves2021succinct], about [positive_circuit]
+
+Up: [satisfiability_weighted], [positive_circuit]
+
+Aliases: WMCS