commit a6a6b7833eb2d610aea47f88f72c9e2874eb4de2
parent 8940bc529c8d967e4eae579129ec43aa484399d0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 4 Jul 2025 16:05:03 +0200
commit with codex
Diffstat:
8 files changed, 20 insertions(+), 1 deletion(-)
diff --git a/3sat b/3sat
@@ -9,3 +9,5 @@ It is [np_complete]
Up: [sat_variants]
See also: [2sat], [schaefers_dichotomy_theorem]
+
+Aliases: 3 SAT
diff --git a/automatic_relation b/automatic_relation
@@ -6,6 +6,8 @@ symbol, i.e., [automaton_synchronous]
- Paper about this: [barcelo2023separating]
- [automatic_relation_algebra]
+Example: the [infinite_binary_tree] is an automatic relation
+
Special case: [recognizable_relations]
Generalization: [deterministic_rational_relations], [rational_relations]
diff --git a/crpq b/crpq
@@ -9,6 +9,8 @@
- [C2RPQ]
- [UCRPQ]
- [conjunctive_context_free_path_query]
+- [regular_query]
+ - [regular_query_with_memory]
[Computational_problems]:
- [CRPQ_containment]
diff --git a/graph_colorability b/graph_colorability
@@ -6,3 +6,5 @@ The [computational_problem] of, given a [graph] G and number k, deciding whether
- [3_colorability]
Up: [computational_problem], [graph_coloring]
+
+Aliases: k colorability
diff --git a/homomorphism b/homomorphism
@@ -4,6 +4,7 @@
- [homomorphism_equivalence]
- [graph_homomorphism]
- [homomorphism_count]
+- [homomorphism_problem]
Variants: [homomorphism_variants]
diff --git a/homomorphism_problem b/homomorphism_problem
@@ -0,0 +1,8 @@
+# Homomorphism problem
+
+The [decision_problem], given two [relational_structures] G and H, of deciding whether there is a [homomorphism] from G to H
+
+This is in [NP], and [NP_hard] even if H is a fixed graph
+- e.g., can code [k_colorability]
+
+Up: [decision_problem], [homomorphism]
diff --git a/query_evaluation b/query_evaluation
@@ -21,4 +21,4 @@
Up: [database_theory_problem]
-See also: [query_language], [enumeration_query_answers]
+See also: [query_language], [enumeration_query_answers], [homomorphism_problem]
diff --git a/regular_query b/regular_query
@@ -12,3 +12,5 @@ Generalizations:
Studied in [reutter2017regular]
Up: [query_language]
+
+Aliases: regular queries
