wiki_research

commit 2c525d39a41e336f9b35fa9004248189a60e797f
parent 2b5689ea7d28d1623cb968bc42c7a9a172d2bd58
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 28 May 2025 18:40:16 +0200

commit with codex

Diffstat:
abiteboul_vianu_theorem
 | 
7
+++++++
descriptive_complexity
 | 
19
+++++++++++++++----
immerman_vardi_theorem
 | 
4
++--
logic_to_capture_ptime
 | 
7
+++++++
mathematics_fields
 | 
1
+
query
 | 
4
+---
query_minimization
 | 
8
++++++++
query_problems
 | 
9
+++++++++
union
 | 
1
+

9 files changed, 51 insertions(+), 9 deletions(-)
diff --git a/abiteboul_vianu_theorem b/abiteboul_vianu_theorem
@@ -0,0 +1,7 @@
+# Abiteboul Vianu theorem
+
+https://en.wikipedia.org/wiki/Abiteboul-Vianu_theorem
+
+[PTIME] is equal to [PSPACE] if and only if [fixed_point_logic] is the same as [partial_fixed_point_logic]
+
+Up: [descriptive_complexity]
diff --git a/descriptive_complexity b/descriptive_complexity
@@ -1,10 +1,21 @@
 # Descriptive complexity
 
-Less active nowadays: https://eccc.weizmann.ac.il//report/2011/151/
+## [Theorems]
+
+- [Abiteboul_Vianu_theorem]
+- [immerman_vardi_theorem] : [first_order] with [least_fixpoint], or [datalog], is [ptime] on [ordered_structures]
+  - cf [order_invariance]
+
+## [Open_problems]
+
+- [logic_to_capture_ptime]
+
+## Subfields
 
-- Abiteboul, Hull, Vianu theorem https://en.wikipedia.org/wiki/Abiteboul-Vianu_theorem
-- [open_problem]: finding a logic that captures [ptime]
 - [description_logics_descriptive_complexity]
-- [immerman_vardi_theorem] : [first_order] with [least_fixpoint], or [datalog], is [ptime] on ordered structures (cf [order_invariance])
+
+## Meta
+
+- Less active field nowadays: https://eccc.weizmann.ac.il//report/2011/151/
 
 Up: [computational_complexity]
diff --git a/immerman_vardi_theorem b/immerman_vardi_theorem
@@ -2,8 +2,8 @@
 
 https://en.wikipedia.org/wiki/Immerman-Vardi_theorem
 
-[datalog] with [negation] characterizes [ptime] on [ordered_structures]
+[datalog] with [negation], or [first_order] with [least_fixpoint], characterizes [ptime] on [ordered_structures]
 
 Up: [datalog]
 
-See also: [abiteboul_vianu_theorem]
+See also: [abiteboul_vianu_theorem], [order_invariance]
diff --git a/logic_to_capture_ptime b/logic_to_capture_ptime
@@ -0,0 +1,7 @@
+# Logic to capture PTIME
+
+[open_problem] in [descriptive_complexity]: finding a logic that captures [ptime]
+
+Up: [descriptive_complexity]
+
+See also: [Immerman_vardi_theorem]
diff --git a/mathematics_fields b/mathematics_fields
@@ -17,5 +17,6 @@ classification [msc]
 - [fourier_analysis]
 - [discrete_mathematics]
 - [statistics]
+- [group_theory]
 
 Up: [mathematics]
diff --git a/query b/query
@@ -9,9 +9,7 @@
 
 ## Problems
 
-- [query_resilience]
-- [query_containment]
-- [minimal_witness]
+[query_problems]
 
 Up: [database_theory]
 
diff --git a/query_minimization b/query_minimization
@@ -0,0 +1,8 @@
+# Query minimization
+
+- [CQ_minimization]
+- [CRPQ_minimization]
+
+Up: [query_problems]
+
+See also: [core]
diff --git a/query_problems b/query_problems
@@ -0,0 +1,9 @@
+# Query problems
+
+- [query_containment]
+- [query_equivalence]
+- [query_minimization]
+- [query_resilience]
+- [minimal_witness]
+
+Up: [query]
diff --git a/union b/union
@@ -3,5 +3,6 @@
 - [union_trick]
 - [disjoint_union]
 - [language_union]
+- [query_union]
 
 Up: [set_theory], [boolean_operator]