commit e90eb22fe04aa9974cca7b44f90ba71c78b9292d
parent 207e37ace8fb86e7b60e292c25e20ab9057e6d02
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 4 Sep 2026 19:37:58 +0200
commit with codex
Diffstat:
15 files changed, 44 insertions(+), 14 deletions(-)
diff --git a/1_turing_reduction b/1_turing_reduction
@@ -0,0 +1,7 @@
+# 1-turing reduction
+
+A [turing_reduction] where we can make at most one [oracle] call
+
+Up: [turing_reduction]
+
+Aliases: 1-turing reduction, one query Turing reduction, one-query Turing reduction
diff --git a/3_dimensional_matching_numerical b/3_dimensional_matching_numerical
@@ -9,6 +9,14 @@ all triples that sum to the same value S/n where S is the sum of all the X Y Z
http://courses.csail.mit.edu/6.892/spring19/scribe/lec2.pdf simply by adding
large values
+still [strongly_NP_hard] even when two of the three sets are {1,2,...,n}, see [yu2004minimizing]
+
+still [strongly_NP_hard] even when all 3n input integers are required to be pairwise distinct
+- cf [hulett2008multigraph] Corollary 8
+- generalized to [ASP_hardness] in [mit2024tetris] Theorem 3
+
See also: [3_dimensional_matching], [3_partition]
Up: [computational_problem]
+
+Aliases: numerical 3DM, N3DM, numerical 3-dimensional matching, numerical 3 dimensional matching
diff --git a/circuit_equivalence b/circuit_equivalence
@@ -3,6 +3,7 @@
The [computational_problem] of deciding, given two [Boolean_circuits], whether they represent the same [Boolean_function]
- [circuit_equivalence_dDNNF]
+- [circuit_equivalence_FBDD]
Up: [Boolean_function_equivalence], [circuit]
diff --git a/computational_complexity b/computational_complexity
@@ -27,6 +27,8 @@
- [counting_complexity]
- [sharpp]
- [complexity_rectangular]
+- [another_solution_problem] (ASP)
+ - [ASP_completeness]
## [database_theory]
diff --git a/de_bruijn_sequence b/de_bruijn_sequence
@@ -4,6 +4,6 @@ https://en.wikipedia.org/wiki/De_Bruijn_sequence
like [universal_word] but for [cyclic_word]
-See also: [universal_word]
+See also: [universal_word], [de_bruijn_graph]
Up: [word_combinatorics]
diff --git a/fbdd b/fbdd
@@ -11,6 +11,10 @@ Generalizations:
- [uFBDD]
- [nFBDD]
+[Computational_problems]:
+
+- [FBDD_equivalence]
+
Up: [bdd]
Aliases: FBDDs
diff --git a/fbdd_equivalence b/fbdd_equivalence
@@ -0,0 +1,7 @@
+# FBDD equivalence
+
+It is known to be in [BPP] but not in [PTIME], see [circuit_zoo]
+
+Up: [fbdd], [circuit_equivalence]
+
+Aliases: equivalence FBDD, circuit equivalence FBDD
diff --git a/hamiltonian_cycle b/hamiltonian_cycle
@@ -1,9 +0,0 @@
-# Hamiltonian cycle
-
-[Computational_problem]: [Hamiltonian_cycle_problem]
-
-Up: [cycle]
-
-See also: [graph_eulerian], [hamiltonian_path]
-
-Aliases: hamiltonian cycles
diff --git a/matching b/matching
@@ -25,7 +25,7 @@ Variants:
Also the [linear_relaxation]: see [fractional_edge_packing]
-See also: [independent_set], [induced_matching], [graph_matching_covered], [deficiency], [partial_bijection]
+See also: [independent_set], [induced_matching], [graph_matching_covered], [deficiency], [partial_bijection], [2_factor]
Up: [graph_substructure]
diff --git a/spanning_tree b/spanning_tree
@@ -5,6 +5,6 @@
See also: [steiner_tree], [spanning_forest]
-Up: [tree], [subgraph]
+Up: [tree], [spanning_subgraph]
Aliases: spanning trees
diff --git a/strongly_np_complete b/strongly_np_complete
@@ -1,6 +1,6 @@
# Strong NP-completeness
-The fact of being [NP_complete] even numbers in the input are represented in unary
+A problem is *strongly NP-complete* if it is in [NP] and it is [strongly_NP_hard]
[strongly_np_complete_list]
diff --git a/strongly_np_complete_list b/strongly_np_complete_list
@@ -4,5 +4,6 @@ List of [strongly_np_complete] [decision_problems]:
- [3_partition]
- [bin_packing]
+- [N3DM]
Up: [strongly_np_complete]
diff --git a/strongly_np_hard b/strongly_np_hard
@@ -0,0 +1,7 @@
+# Strongly NP hard
+
+A [computational_problem] is *strongly NP-hard* if it [NP_hard] even when numbers in the input are represented in unary
+
+See also: [strongly_np_complete]
+
+Up: [computational_complexity]
diff --git a/subgraph b/subgraph
@@ -6,4 +6,4 @@ Up: [graph]
Aliases: subgraphs
-See also: [subinstance], [subdatabase], [induced_subgraph], [isometric_subgraph]
+See also: [subinstance], [subdatabase], [induced_subgraph], [isometric_subgraph], [spanning_subgraph]
diff --git a/turing_reduction b/turing_reduction
@@ -7,6 +7,8 @@ A [reduction] which uses target problem as [oracle]
Not always very different from [many_one_reductions] for [counting_problems]
- cf argument https://dbt.zulipchat.com/#narrow/stream/417238-Dagstuhl-24032/topic/Open.20problems/near/425331364
+Restricted case: [1_turing_reduction]
+
Up: [reduction]
See also: [alan_turing], [many_one_reduction]
