commit 81aff607f96495d564aaaa48caffa418674af5df
parent b60de1effc5516efdec845e641dd2064bb1cd692
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 22 Apr 2025 01:20:40 +0200
commit with codex
Diffstat:
8 files changed, 36 insertions(+), 2 deletions(-)
diff --git a/dynamic_membership b/dynamic_membership
@@ -7,6 +7,8 @@ The [membership_problem] on [dynamic_data]
[dynamic_membership_extensions]
+- [dynamic_membership_dynfo]
+
See also: [dynamic_complexity], [pattern_matching], [incremental_maintenance], [dynamic_data_word], [pattern_matching_dynamic]
Up: [incremental_maintenance]
diff --git a/induced_subgraph b/induced_subgraph
@@ -2,7 +2,7 @@
A [subgraph] of a [graph] defined by taking a [subset] U of [vertices] and taking the [edges] between the [vertices] of U
-See also: [subgraph], [graph_minor], [induced_subhypergraph], [induced_cycle]
+See also: [subgraph], [graph_minor], [induced_subhypergraph], [induced_cycle], [induced_subinstance]
Up: [graph]
diff --git a/minimal_witness b/minimal_witness
@@ -13,4 +13,4 @@ easy for [conjunctive_query_full], so hardness comes from [projection]
Up: [database_theory]
-See also: [query_resilience]
+See also: [query_resilience], [smallest_synthetic_witness], [synthetic_witness]
diff --git a/smallest_synthetic_witness b/smallest_synthetic_witness
@@ -0,0 +1,9 @@
+# Smallest synthetic witness
+
+Given a [query] Q and [query_answer] A, what is the [synthetic_witness] of minimum [cardinality]?
+
+Up: [computational_problem], [synthetic_witness]
+
+See also: [synthetic_witness_existence], [minimal_witness]
+
+Aliases: Minimal synthetic witness
diff --git a/subgraph b/subgraph
@@ -5,3 +5,5 @@ A [graph] obtained from another [graph] by keeping the same [vertices] and a [su
Up: [graph]
Aliases: subgraphs
+
+See also: [subinstance]
diff --git a/synthetic_witness b/synthetic_witness
@@ -0,0 +1,11 @@
+# Synthetic witness
+
+Given a [query] Q and [query_answer] A, a *synthetic witness* is a [database] D such that Q(D) = A
+
+- [esmailpour2025synthetic]
+ - [synthetic_witness_existence]
+ - [minimal_synthetic_witness]
+
+See also: [minimal_witness]
+
+Up: [database_theory]
diff --git a/synthetic_witness_existence b/synthetic_witness_existence
@@ -0,0 +1,9 @@
+# Synthetic witness existence
+
+Given a [query] Q and [query_answer] A, does there exist a [synthetic_witness]
+
+Studied in [esmailpour2025smallest]
+
+Up: [computational_problem], [synthetic_witness]
+
+See also: [Satisfiability]
diff --git a/theorem b/theorem
@@ -21,6 +21,7 @@ A [result] in [mathematics], recognized as challenging to prove
- [Immerman_Vardi_theorem]
- [Koenig's_theorem]
- [Ladner's_theorem]
+- [Los_Tarski_theorem]
- [Mantel's_theorem]
- [Menger's_theorem]
- [Nicomaque's_theorem]
