wiki_research

commit 36c46820b64d43dd492b13a0a65fc8a505e243f4
parent 87f86f82a9d8f1a78cf937fdf47a0be64086d446
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Thu, 12 Jun 2025 14:53:02 +0200

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

Diffstat:
algorithm_randomized
 | 
2
+-
fpras_bpp
 | 
8
+++++---
koenigs_theorem
 | 
10
++++++----
maximum_matching
 | 
2
++
planar_sat
 | 
7
+++++++
theorem
 | 
2
+-
vertex_cover
 | 
4
++--

7 files changed, 24 insertions(+), 11 deletions(-)
diff --git a/algorithm_randomized b/algorithm_randomized
@@ -14,6 +14,6 @@ Techniques used for randomized algorithms:
 
 Up: [algorithms]
 
-See also: [fpras], [rp], [complexity_random], [randomness], [derandomization]
+See also: [fpras], [rp], [complexity_random], [randomness], [derandomization], [randomized_reduction]
 
 Aliases: randomized
diff --git a/fpras_bpp b/fpras_bpp
@@ -1,11 +1,13 @@
 # FPRAS BPP
 
-[theorem]: if a [counting_problem] admits an [fpras], then the corresponding [decision_problem] of testing if the count is >0 is in [bpp]
+[theorem]: if a [counting_problem] admits an [FPRAS], then the corresponding [decision_problem] of testing if the count is >0 is in [BPP]
 - for [satisfiability_boolean] for instance:
-  - if [sharp_satisfiability] admits an [fpras], then [satisfiability_boolean] is in [bpp]
+  - if [sharp_satisfiability] admits an [fpras], then [satisfiability_boolean] is in [BPP]
 - this is specific to >0 and does not work, say, for <2^n (problem of relative
   error)
 
-Proof: with proba 3/4 your [fpras] "works", and "works" here means "returns exactly the correct value"
+Proof: with proba 3/4 your [FPRAS] "works", and "works" here means "returns exactly the correct value"
 
 Up: [result] on [fpras]
+
+Aliases: FPRAS BPP correspondance theorem
diff --git a/koenigs_theorem b/koenigs_theorem
@@ -1,9 +1,11 @@
 # König's theorem
 
-In a [graph_bipartite], the [maximum_matching] size and the [minimum_vertex_cover] size are the same.
+https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)
 
-There is also a weighted version: Egerváry's theorem
+In a [bipartite_graph], the [maximum_matching] size and the [minimum_vertex_cover] size are the same.
 
-Generalization to [hypergraph] if they are [hypergraph_balanced]
+There is also a weighted version: [Egerváry's_theorem]
 
-Up: [vertex_cover]
+Generalization to [hypergraphs] if they are [hypergraph_balanced]
+
+Up: [theorem] on [vertex_cover]
diff --git a/maximum_matching b/maximum_matching
@@ -10,3 +10,5 @@ Also [online_algorithm] for maximum matching
 Up: [computational_problem] on [matching]
 
 See also: [alternating_path]
+
+Aliases: maximum matchings
diff --git a/planar_sat b/planar_sat
@@ -0,0 +1,7 @@
+# Planar SAT
+
+https://en.wikipedia.org/wiki/Planar_SAT
+
+still [NP_hard]
+
+Up: [sat_variants], [planar_graph]
diff --git a/theorem b/theorem
@@ -12,7 +12,7 @@ A [result] in [mathematics], recognized as challenging to prove
 - [Eggan's_theorem]
 - [Four_color_theorem]
 - [Fine_Wilf_theorem]
-- [fpras_bpp]
+- [fpras_bpp_correspondance_theorem]
 - [friendship_theorem]
 - [Goedel's_incompleteness_theorem]
 - [Grotzsch's_theorem]
diff --git a/vertex_cover b/vertex_cover
@@ -18,9 +18,9 @@ A vertex cover in a [graph] is a subset of vertices such that every edge is inci
 
 - [minimum_vertex_cover]
 
-## [theorem]s
+## [theorems]
 
-- [koenigs_theorem] in [graph_bipartite]
+- [koenigs_theorem] in [graph_bipartite] relates vertex covers to [maximum_matchings]
 
 ## Connections