commit 8034d49ca7eb1ba8d42b5950aa541d9e74ceb74e
parent fdc683fba66fd7376d08fadbb310d72d6fdbd4f2
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 11 Oct 2025 20:44:49 +0200
commit with codex
Diffstat:
11 files changed, 70 insertions(+), 12 deletions(-)
diff --git a/complement_class b/complement_class
@@ -0,0 +1,9 @@
+# Complement class
+
+In [computational_complexity], the [complement_class] of a [complexity_class] of [decision_problems] C is the [complexity_class] of those [decision_problems] that are the [complements] of the [decision_problems] of C
+
+It is *not* the [complement] of C
+
+For instance, [coNP] is the complement class of [NP]
+
+Up: [complementation]
diff --git a/complementation b/complementation
@@ -3,7 +3,8 @@
- [ddnnf_complementation]
- [graph_complementation]
- [language_complementation]
+- [complement_class]
Up: [logic], [boolean_operator]
-Aliases: complement
+Aliases: complement, complements
diff --git a/conp b/conp
@@ -1,8 +1,12 @@
-# Conp
+# CoNP
[Decision_problems] whose [complementation] is in [nptime]
+It is the [complement_class] of [NP]
+
- [conp_hard]
- [conp_complete]
See also: [nptime], [np_cap_conp]
+
+Aliases: co NP
diff --git a/isometric_subgraph b/isometric_subgraph
@@ -0,0 +1,7 @@
+# Isometric subgraph
+
+Mentioned in [baste2025polynomial]
+
+A [subgraph] H of a graph G is *isometric* if every [shortest_path] in H is also a [shortest_path] in G
+
+Up: [subgraph]
diff --git a/k_ambiguous_automaton b/k_ambiguous_automaton
@@ -3,3 +3,5 @@
- [word_automaton_k_unambiguous]
Up: [k_unambiguous]
+
+Aliases: bounded ambiguity automaton, bounded ambiguity automata
diff --git a/probabilistic_automata_bounded_ambiguity b/probabilistic_automata_bounded_ambiguity
@@ -0,0 +1,5 @@
+# Probabilistic automata bounded ambiguity
+
+see [fijalkow2022probabilistic]
+
+Up: [probabilistic_automata], [bounded_ambiguity_automata]
diff --git a/shortest_path b/shortest_path
@@ -0,0 +1,27 @@
+# Shortest path
+
+A [path] in a [graph] whose [path_length] (or [path_weight]) is [minimal]
+
+Weights:
+- [graph_unweighted]
+- [graph_weighted]
+
+Types:
+- [single_source_shortest_path]
+- [all_pairs_shortest_path]
+
+Related:
+- [shortest_path_practice]
+
+Variants:
+- [shortest_path_almost]
+
+[shortest_path_algorithm]
+
+[shortest_path_enumeration]
+
+Up: [graph_problem]
+
+See also: [minmax_path], [reachability], [transitive_closure]
+
+Aliases: shortest paths
diff --git a/shortest_path_algorithm b/shortest_path_algorithm
@@ -1,8 +0,0 @@
-# Shortest path algorithm
-
-For [all_pairs_shortest_path]:
-- [Floyd_Warshall_algorithm]
-
-For [single_source_shortest_path]: [single_source_shortest_path_algorithm]
-
-Up: [shortest_path]
diff --git a/subgraph b/subgraph
@@ -6,4 +6,4 @@ Up: [graph]
Aliases: subgraphs
-See also: [subinstance], [subdatabase], [induced_subgraph]
+See also: [subinstance], [subdatabase], [induced_subgraph], [isometric_subgraph]
diff --git a/unambiguous_computation b/unambiguous_computation
@@ -0,0 +1,9 @@
+# Unambiguous computation
+
+[Course_notes]: [vijaykumar2016unambiguous]
+
+- [UP]
+- also analogues for [space_complexity]
+- also analogues for [NL]
+
+Up: [unambiguity], [computational_complexity]
diff --git a/up b/up
@@ -11,4 +11,6 @@ Generalizations:
- [FewP]
- [US]
-Up: [nptime], [unambiguity], [complexity_class]
+[Complement]: [coUP]
+
+Up: [nptime], [unambiguous_computation], [complexity_class]
