wiki_research

commit 57aab99f0ba9ad5fd4b770e9777040084f2905fe
parent 8c5731e1a62cecadd941aa725372a7f1a808f936
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon, 27 Oct 2025 10:19:05 +0100

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
computing
 | 
2
+-
geometry
 | 
1
+
gql
 | 
1
+
graph_family
 | 
2
++
leaf
 | 
2
+-
leaf_power
 | 
12
++++++++++++
unambiguous_sigma2
 | 
9
+++++++++
up
 | 
2
++

8 files changed, 29 insertions(+), 2 deletions(-)
diff --git a/computing b/computing
@@ -7,6 +7,6 @@ https://en.wikipedia.org/wiki/Unconventional_computing
 - [quantum_computing]
 - [dionaea_muscipula_computer]
 
-See also: [computer], [computability]
+See also: [computer], [computability], [computing_center]
 
 Up: [computer_science]
diff --git a/geometry b/geometry
@@ -4,6 +4,7 @@
 - arrangements of spheres "kissing number"
 - [moving_sofa_problem]
 - [computational_geometry]
+- [nopert]
 
 - [square]
 - [circle]
diff --git a/gql b/gql
@@ -2,5 +2,6 @@
 
 - [francis2023researchers]: explanation GQL
 - [francis2023gpc] introduces [gpc] which is equivalent to GQL but easier to understand
+- [figueira2025complexity] studies the [computational_complexity] of [query_evaluation]
 
 Up: [graph_query_languages_standards]
diff --git a/graph_family b/graph_family
@@ -40,6 +40,8 @@ A (generally [infinite]) set of [graphs]
 - [friendship_graph]
 - [berge_graph]
 
+- [leaf_power]
+
 May have the property of being [graph_class_hereditary]
 
 Up: [graph]
diff --git a/leaf b/leaf
@@ -4,6 +4,6 @@
 
 Up: [tree]
 
-See also: [internal_node]
+See also: [internal_node], [leaf_power]
 
 Aliases: leaves
diff --git a/leaf_power b/leaf_power
@@ -0,0 +1,12 @@
+# Leaf power
+
+A [graph] where there exists a [tree] and threshold k such that the [edges] of the graph connect the [vertices] at [distance] at most k in the tree
+
+[Hamiltonian_path] on them is in [PTIME] for each fixed k but [NP_hard] in general
+https://cstheory.stackexchange.com/questions/52305/complexity-of-finding-a-path-visiting-all-leaves-on-a-tree-while-respecting-a-di/52315
+
+Variant: [pairwise_compatibility_graph], i.e., the distance is between two thresholds
+
+Recognizing these graphs is [NP_hard] [duprelatour2025recognizing]
+
+Up: [graph_family]
diff --git a/unambiguous_sigma2 b/unambiguous_sigma2
@@ -0,0 +1,9 @@
+# Unambiguous sigma2
+
+The [Sigma2] class with a unique choice of existential
+
+Studied in [gilboa2025complexity]
+
+See also: [up]
+
+Up: [sigma2]
diff --git a/up b/up
@@ -14,3 +14,5 @@ Generalizations:
 [Complement]: [coUP]
 
 Up: [nptime], [unambiguous_computation], [complexity_class]
+
+See also: [unambiguous_sigma2]