commit 57cbd458ea7f5eeb2d975c293d855f6e0798426c
parent 6b1ec23969c8c44300f193fdd4bed9c187c64b0f
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 9 Oct 2025 21:49:22 +0200
commit with codex
Diffstat:
7 files changed, 10 insertions(+), 4 deletions(-)
diff --git a/counting_problem b/counting_problem
@@ -15,6 +15,7 @@
- [sharp_nfa], cf [arenas2020efficient]
- [sharp_ufa]
- [sharp_dfa]
+- [modular_counting]
Up: [computational_problem], [counting]
diff --git a/datalog b/datalog
@@ -47,6 +47,7 @@
- [incremental_maintenance_datalog]
- [datalog_grounding]
- [datalog_rewriting]
+- [datalog_course]
Up: [query_language]
diff --git a/level_ancestor b/level_ancestor
@@ -1,10 +1,11 @@
# Level ancestor
-Do [preprocessing] on [tree] and compute [data_structure] such that given a [node] and integer d you can find the [ancestor] of the [node] at distance d from it (or, equivalently, at specified [depth])
+Do [preprocessing] on a [tree] and compute a [data_structure] such that given a [node] and integer d you can find the [ancestor] of the [node] at distance d from it (or, equivalently, at specified [depth])
Can be done with linear preprocessing of the tree and constant query time
- cf for instance [bender2004level]
- [alstrup2000improved] for [trees] under [updates], and to find the node with minimum weight on the path between two nodes when the tree is weighted
-- [bender2003level]: simplified version of the problem (decompose into [microtrees])
+- [bender2003level]: simplified version of the problem
+ - decompose into [microtrees]
Up: [data_structure]
diff --git a/matrix_mortality b/matrix_mortality
@@ -4,6 +4,7 @@
- results in [benameur2024complexity]
- [undecidable] already for 3 by 3 matrices
- for [Boolean_matrices], [pspace_complete]
+- [potapov2017decidability]: [decidability] for 2 by 2 [nonsingular_matrices]
Up: [matrix]
diff --git a/mod_k_p b/mod_k_p
@@ -7,3 +7,5 @@ https://complexityzoo.net/Complexity_Zoo:M#modkp
For k=2, [parity_p]
Up: [parity_p]
+
+See also: [modular_counting]
diff --git a/optimization b/optimization
@@ -11,4 +11,4 @@
Up: [computer_science]
-See also: [inefficiency], [search_space]
+See also: [inefficiency], [search_space], [scheduling]
diff --git a/parity_p b/parity_p
@@ -10,4 +10,4 @@ Generalization to other moduli: [mod_k_p]
Up: [parity], [complexity_class]
-See also: [parity_fine_grained], [Z_2Z], [parity_L]
+See also: [parity_fine_grained], [Z_2Z], [parity_L], [modular_counting]
