commit 04e334bd126411e1c37b79c71a43ddd7e54531a7
parent 9f6a10d81830346d287a943f5316cfaead8d9ad3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 18 Mar 2026 12:10:12 +0100
commit with codex
Diffstat:
21 files changed, 52 insertions(+), 29 deletions(-)
diff --git a/acc b/acc
@@ -1,6 +1,6 @@
# Acc
-Like [ac] circuits, so polynomial size unbounded [fan_in] and [depth] in O(log^i n), but adds gates that can count modulo a fixed integer
+Like [ac] circuits, so polynomial size unbounded [fan_in] and [depth] in O(log^i n), but adds [modulo_gates] that can count modulo a fixed integer
- contains [parity]
- [acc0]: constant [depth]
diff --git a/acc0 b/acc0
@@ -1,9 +1,11 @@
-# Acc0
+# ACC0
-[acc] circuit with constant [depth]
+[ACC] circuit with constant [depth]
-strict superset of [ac0], separated by [parity]
+strict superset of [AC0], separated by [parity]
-Up: [acc]
+Shown by [Ryan_Williams] that there is a problem in [NEXP] which is not in (non-uniform) [ACC0]
-See also: [ac0]
+Up: [ACC]
+
+See also: [AC0], [modulo_gates]
diff --git a/axiom b/axiom
@@ -4,4 +4,4 @@ The initial [nonterminal] of a [context_free_grammar]
Up: [context_free_grammar]
-See also: [initial_state]
+See also: [initial_state], [reverse_mathematics]
diff --git a/directed_acyclic_graph b/directed_acyclic_graph
@@ -1,9 +1,11 @@
# Directed acyclic graph (DAG)
-[graph_directed] which does not contain [cycle]
+[directed_graph] which does not contain a [cycle]
-- [topological_sorting]
+We can apply [topological_sorting] on such graphs
-Up: [graph_directed]
+Up: [directed_graph], [acyclic_graph]
Aliases: DAG, DAGs
+
+See also: [SLP_compressed_tree]
diff --git a/distance b/distance
@@ -7,3 +7,5 @@
- [ultrametric]
Up: [mathematics]
+
+See also: [metric_space]
diff --git a/enumeration b/enumeration
@@ -21,6 +21,7 @@ https://en.wikipedia.org/wiki/Enumeration_algorithm
- [enumeration_diversity]
- [enumeration_ordered]
- [incremental_maintenance_enumeration]
+- [enumeration_practice]
Up: [algorithms]
diff --git a/enumeration_tasks b/enumeration_tasks
@@ -22,5 +22,6 @@
- [enumeration_csp] ([christoph_berkholz])
- [enumeration_topological_sort]
- https://cstheory.stackexchange.com/questions/36334/enumerating-topological-sorts-of-a-vertex-labeled-dag
+- [enumeration_valuations]
Up: [enumeration]
diff --git a/exptime b/exptime
@@ -8,4 +8,4 @@ in 2^{P(n)} for P a [polynomial]
Up: [complexity_time_classes]
-See also: [2exptime], [EXPTIME_complete], [nexptime]
+See also: [2exptime], [EXPTIME_complete], [NEXPTIME]
diff --git a/logic b/logic
@@ -74,6 +74,6 @@
Up: [mathematics], [theoretical_computer_science]
-See also: [knowledge_representation], [reasoning], [logic_applications], [expressiveness]
+See also: [knowledge_representation], [reasoning], [logic_applications], [expressiveness], [reverse_mathematics]
Aliases: logics
diff --git a/logspace b/logspace
@@ -8,7 +8,7 @@ Variant [polyl]: solved with [polylogarithmic] [complexity_space]
Variant [NL] ([nondeterminism])
-Variant [SL]: symmetric logspace, class of problems reducible to undirected [reachability], showed to be equal to [logspace] by [reingold]
+Variant [SL]: symmetric logspace, class of problems reducible to [undirected_reachability], showed to be equal to [logspace] by [reingold]
- for [2sat] corresponds to the case where exactly one literal in each clause must hold
Up: [complexity_class]
diff --git a/metacomplexity b/metacomplexity
@@ -5,3 +5,5 @@ https://simons.berkeley.edu/programs/Meta-Complexity2023
Complexity of problems where we ask what is the complexity of an input, e.g., [kolmogorof_complexity], [minimum_circuit_size_problem]
Up: [computational_complexity]
+
+See also: [reverse_mathematics]
diff --git a/nc1 b/nc1
@@ -1,13 +0,0 @@
-# NC1
-
-https://en.wikipedia.org/wiki/NC_(complexity)
-
-circuits with [polynomial] [circuit_size] and [polylogarithmic] [depth]
-
-NC1 circuits equivalent to polynomial-size uniform family of [formula_boolean]
-
-https://en.wikipedia.org/wiki/NL_(complexity) says we have:
-
-[nc1] included in [logtime] included in [nlogtime] included in [nc2]
-
-Up: [nc], [circuit_complexity]
diff --git a/nexptime b/nexptime
@@ -0,0 +1,9 @@
+# NEXPTIME
+
+[nondeterministic] [EXPTIME]
+
+See also: [EXPTIME]
+
+Up: [complexity_time_classes]
+
+Aliases: NEXP
diff --git a/satisfiability b/satisfiability
@@ -10,6 +10,6 @@ The *satisfiability problem* is a [decision_problem] in [logic]: given a [logica
Tools: [sat_solver]
-See also: [strong_exponential_time_hypothesis], [satisfiability_boolean], [tautology], [automaton_emptiness], [satisfiability_modulo_theory], [equisatisfiability]
+See also: [strong_exponential_time_hypothesis], [satisfiability_boolean], [tautology], [automaton_emptiness], [satisfiability_modulo_theory], [equisatisfiability], [enumeration_valuations]
Up: [computational_problem]
diff --git a/st_reachability_undirected b/st_reachability_undirected
@@ -2,8 +2,9 @@
Given an [undirected_graph] and two [vertices] s and t, decide if there is an [undirected_path] between s and t
-[Complete] for [SL]
+[Complete] for [SL], and shown in [L] by [reingold2008undirected]; but open if
+[L] = [RL]
Up: [st_reachability]
-Aliases: undirected st-reachability
+Aliases: undirected st-reachability, undirected reachability
diff --git a/straight_line_program b/straight_line_program
@@ -6,6 +6,8 @@ essentially a [context_free_grammar] that generates a single [string]: [acyclici
- [smallest_grammar_problem]
- [slp_balancing]
+Generalization: [SLP_compressed_trees]
+
Up: [string_compression]
See also: [forest_straight_line_program]
diff --git a/suffix_free_language b/suffix_free_language
@@ -2,6 +2,8 @@
A [formal_language] L is *suffix-free* if, whenever u and v are in L and u is a [suffix] of v, then u = v
+[State_complexity] of suffix-free languages: cf [han2009state]
+
Up: [suffix]
See also: [prefix_free_language], [bifix_free_language]
diff --git a/tree b/tree
@@ -73,6 +73,7 @@
- [multitree]
- [out_tree] as a [directed_graph]
- [tree_weighted]
+- [SLP_compressed_tree]
Up: [data_structure]
diff --git a/treedepth b/treedepth
@@ -4,4 +4,6 @@ https://en.wikipedia.org/wiki/Tree-depth
The *treedepth* of an [undirected_graph] G is the minimum [forest_height] of an [elimination_forest] for G
+Generalization: [weighted_treedepth]
+
Up: [width_measure]
diff --git a/treedepth_weighted b/treedepth_weighted
@@ -0,0 +1,7 @@
+# Weighted treedepth
+
+Can be [NP_complete], cf [dirks2025weighted]
+
+Up: [treedepth]
+
+Aliases: Weighted treedepth
diff --git a/ultrametric b/ultrametric
@@ -3,3 +3,5 @@
[metric] satisfying [triangle_inequality_strong]
Up: [distance]
+
+See also: [metric_space]
