commit 2a38da96d044cc1788665d49c88e3120dc399f9a
parent 1461165678175433b9689f151a39de534df16199
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 16 Jun 2025 08:41:13 +0200
mv
Diffstat:
2 files changed, 16 insertions(+), 18 deletions(-)
diff --git a/minimal_witness b/minimal_witness
@@ -1,18 +0,0 @@
-# Minimal witness
-
-#todo "minimum witness"?
-
-Find the smallest subset of a [relational_database] that satisfies a [query]
-- formally, for query Q and database D, find smallest subset D' of D giving the same result
-- [approximation]: find a subset of tuples giving the same results which is within a [approximation_multiplicative] factor of the size of the optimal subset
-
-easy for [conjunctive_query_full], so hardness comes from [projection]
-
-- [miao2019explaining], with [ptime] algorithm for a specific tuple
-- [hu2023finding], [best_paper_award] at [icdt_2024]
-
-Up: [database_theory]
-
-See also: [query_resilience], [smallest_synthetic_witness], [synthetic_witness]
-
-Aliases: minimum witness, smallest witness
diff --git a/smallest_witness b/smallest_witness
@@ -0,0 +1,16 @@
+# Minimal witness
+
+Find the smallest subset of a [relational_database] that satisfies a [query]
+- formally, for query Q and database D, find smallest subset D' of D giving the same result
+- [approximation]: find a subset of tuples giving the same results which is within a [approximation_multiplicative] factor of the size of the optimal subset
+
+easy for [conjunctive_query_full], so hardness comes from [projection]
+
+- [miao2019explaining], with [ptime] algorithm for a specific tuple
+- [hu2023finding], [best_paper_award] at [icdt_2024]
+
+Up: [database_theory]
+
+See also: [query_resilience], [smallest_synthetic_witness], [synthetic_witness]
+
+Aliases: minimum witness, minimal witness
