commit 94f279bd36ebb42cabdf262d066953b3d3a2feba
parent 4ce11943c0f699fa7daaca77b44fcfa1aae3a1d4
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 27 Sep 2026 19:13:52 +0200
commit with codex
Diffstat:
17 files changed, 69 insertions(+), 25 deletions(-)
diff --git a/approximation b/approximation
@@ -1,10 +1,12 @@
# Approximation
-Two kinds of approximation:
+Three kinds of approximation:
+- [fixed_ratio_approximation]
- [approximation_additive]: section 3.2.1 [souihli2012querying] [monte_carlo] [hoeffdings_inequality]
- [approximation_multiplicative]: what follows is about those
Complexity classes [approximation_class]:
+- [APX]
- [FPRAS]
- [PRAS]
- etc.
diff --git a/approximation_problem b/approximation_problem
@@ -2,6 +2,7 @@
- [all_pairs_shortest_path_approximate]
- [sharp_satisfiability_approximate]
+- [vertex_cover_approximate]
See also: [fpras], [approximation_algorithm]
diff --git a/apx b/apx
@@ -1,22 +0,0 @@
-# APX
-
-class of [nptime] [optimization_problem] with [approximation] in polynomial time
-with a ratio bounded by a constant
-- analogue but for [counting_problem]?
-
-Being in this class is weaker than existence of a [ptas], and if P neq NP then there are problems in [apx] that do not have a [ptas]
-
-- [apx]-hard: as hard as problems that can be approximated within constant factor
-- [log_apx]-hard: as hard as problems that can be approximated within a log factor
-- [poly_apx]-hard:
- - for instance [maximum_independent_set]
-- on a [apx] subsetneq [log_apx] subsetneq [poly_apx]
- - et ces inclusions sont strictes si P neq NP, reference [escoffier2007structures]
-
-reference: [lee2021classifying]
-
-[apx_counting]
-
-See also: [approximation_algorithm]
-
-Up: [complexity_class]
diff --git a/arity_two_signature b/arity_two_signature
@@ -0,0 +1,9 @@
+# Arity two signature
+
+A [relational_signature] where the maximal [relation_arity] of a [relation_name] is 2
+
+Can be seen as [directed_graphs] with [vertex_coloring] and [edge_coloring] and allowing [self_loops]
+
+Up: [relational_signature]
+
+Aliases: arity-two signature, graph signature
diff --git a/bag_semantics b/bag_semantics
@@ -4,4 +4,4 @@ The [query_semantics] where [queries] results have [duplicates], i.e., a [multis
Up: [query_semantics]
-See also: [set_semantics], [containment_bag_semantics], [multiset], [bag]
+See also: [set_semantics], [containment_bag_semantics], [multiset], [bag], [homomorphism_counts]
diff --git a/connected_cq b/connected_cq
@@ -2,6 +2,10 @@
A [CQ] whose [Gaifman_graph] is [connected]
+If the CQ is [query_minimal], this is equivalent to saying that all [minimal_models] are [connected_instances]
+
Up: [conjunctive_query], [query_connected]
See also: [connected_UCQ], [connected_homomorphism_closed_query]
+
+Aliases: connected CQs
diff --git a/connected_homomorphism_closed_query b/connected_homomorphism_closed_query
@@ -0,0 +1,9 @@
+# Connected homomorphism closed query
+
+A [homomorphism_closed] query which is [connected_query] in the sense that all [minimal_models] of the query are [connected_relational_instances]
+
+- equivalently, it is an infinite [query_disjunction] of [connected_CQs]
+
+Up: [homomorphism_closed], [connected_query]
+
+Aliases: connected UCQinf
diff --git a/connected_query b/connected_query
@@ -0,0 +1,11 @@
+# Connected query
+
+A [query] which is [connected] in the sense that all [minimal_models] are [connected_relational_instances]
+
+- [connected_homomorphism_closed_query]
+- [connected_CQ]
+- [connected_UCQ]
+
+Up: [query]
+
+Aliases: query connected
diff --git a/counting_query_answers b/counting_query_answers
@@ -9,3 +9,5 @@ The [counting_problem] of [counting] the answers to a [query]
Up: [counting_problem]
Aliases: query answer counting, answer counting
+
+See also: [homomorphism_counts_problem]
diff --git a/dag_path_length b/dag_path_length
@@ -13,4 +13,6 @@ Can be solved via [Boolean_matrix_multiplication]
Up: [path_length], [directed_acyclic_graph]
-See also: [bringmann2024nfa]
+See also: [bringmann2024nfa], [counting_path_dag]
+
+Aliases: path length DAG
diff --git a/directed_acyclic_graph b/directed_acyclic_graph
@@ -4,6 +4,8 @@
We can apply [topological_sorting] on such graphs
+Some tasks become tractable, e.g., [counting_paths_DAG]
+
Up: [directed_graph], [acyclic_graph]
Aliases: DAG, DAGs
diff --git a/homomorphism_closed b/homomorphism_closed
@@ -8,6 +8,7 @@ A [query] Q is *closed under [homomorphism]* if the following holds:
Special case:
- [connected_homomorphism_closed_query]
+- [unbounded_homomorphism_closed_query]
Up: [closure] under [homomorphism]
diff --git a/query b/query
@@ -10,6 +10,7 @@
- [query_constants] / [constant_free_query]
- [query_match]
- [minimal_match]
+- [connected_query]
## Problems
diff --git a/query_match b/query_match
@@ -9,3 +9,5 @@ A *query match* is a [homomorphic_image] of a *query* in a [database_instance]
Up: [query]
Aliases: match, matches, query matches
+
+See also: [query_model]
diff --git a/relational_signature b/relational_signature
@@ -0,0 +1,9 @@
+# Relational signature
+
+A finite set of [relation_names] with associated [relation_arity]
+
+Can be fixed, or can be part of the input, or can be part of the input but with a fixed maximal [relation_arity]
+
+- [arity_two_signature]
+
+Up: [Database_theory_concepts]
diff --git a/todas_theorem b/todas_theorem
@@ -2,6 +2,8 @@
https://en.wikipedia.org/wiki/Toda%27s_theorem
+[toda1992polynomial]
+
The [polynomial_hierarchy] is included in [P_PP] ([P] with a [PP] [oracle])
This implies that the [polynomial_hierarchy] is included in [P_sharpP] ([P] with a [sharpP] [oracle])
diff --git a/unbounded_homomorphism_closed_query b/unbounded_homomorphism_closed_query
@@ -0,0 +1,9 @@
+# Unbounded homomorphism closed query
+
+A [homomorphism_closed] which is [unbounded_query], i.e., not equivalent to a [UCQ]
+
+[PQE] for such queries on [arity_two_signatures] is always [sharpP_hard] in [data_complexity] by [amarilli2022dichotomy]
+
+Up: [homomorphism_closed], [unbounded_query]
+
+Aliases: Unbounded homomorphism closed queries
