commit 351c5507982f92f94c4e4d9b070e1eb43a210dad
parent e25bbade13a4bec39b049a1894c3925b8f58a73b
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 16 May 2025 14:50:01 +0200
commit with codex
Diffstat:
10 files changed, 56 insertions(+), 2 deletions(-)
diff --git a/complexity b/complexity
@@ -4,6 +4,7 @@
- [circuit_complexity]
- [state_complexity]
- [kolmogorov_complexity]
+- [dichotomy]
Up: [theoretical_computer_science]
diff --git a/dichotomy b/dichotomy
@@ -0,0 +1,13 @@
+# Dichotomy
+
+A [theorem] of the form: considering this family of [computational_problems], for some the problem is in [PTIME] for the others it is [NP_complete]
+- can also be posed for other complexity classes
+- or with more complexity regimes, e.g., [trichotomy]
+
+- [dichotomy_list]
+
+The [metadichotomy] is the [computational_problem] of deciding which case of the dichotomy applies
+
+Up: [complexity]
+
+Aliases: dichotomies
diff --git a/dichotomy_list b/dichotomy_list
@@ -0,0 +1,9 @@
+# Dichotomy list
+
+- [berkholz2023dichotomy]
+- [regular_expression_matching_dichotomy]
+- [schaefers_dichotomy_theorem]
+- [bagan2020trichotomy] (a [trichotomy])
+- [feder_vardi_conjecture]
+
+Up: [dichotomy]
diff --git a/disjunctive_normal_form_orthogonal b/disjunctive_normal_form_orthogonal
@@ -11,4 +11,4 @@ note that necessarily the clauses (all except at most one) must be big (at least
Up: [disjunctive_normal_form]
-Aliases: unambiguous DNF, unambiguous DNFs
+Aliases: unambiguous DNF, unambiguous DNFs, orthogonal DNF, orthogonal DNFs
diff --git a/max_sat b/max_sat
@@ -12,3 +12,5 @@ Special case: [max_2sat]
Up: [sat_variants]
See also: [satisfiability_weighted]
+
+Aliases: MAXSAT
diff --git a/metadichotomy b/metadichotomy
@@ -0,0 +1,7 @@
+# Metadichotomy
+
+The [computational_problem] of deciding which case of a [dichotomy] result applies
+
+Up: [dichotomy]
+
+Aliases: meta_dichotomy
diff --git a/obdd b/obdd
@@ -10,3 +10,5 @@ A [deterministic] [bdd] with a [variable_order]
Up: [bdd]
See also: [fbdd]
+
+Aliases: OBDDs
diff --git a/satisfiability_weighted_knowledge_compilation b/satisfiability_weighted_knowledge_compilation
@@ -0,0 +1,11 @@
+# Satisfiability weighted knowledge compilation
+
+For which [knowledge_compilation_circuit_classes] is [satisfiability_weighted] tractable?
+
+Should be tractable for [OBDDs]: [satisfiability_weighted_obdds]
+
+- [satisfiability_weighted_dnnf]
+- [satisfiability_weighted_ddnnf]
+- [satisfiability_weighted_ddnnf_negation]
+
+Up: [satisfiability_weighted], [knowledge_compilation]
diff --git a/satisfiability_weighted_obdds b/satisfiability_weighted_obdds
@@ -0,0 +1,9 @@
+# Satisfiability weighted obdds
+
+Can do [satisfiability_weighted] for [OBDDs] by [product_construction] in the case of [unary] weights
+
+Also following [topological_sort], cf <2jzxunmsdpibv6fugq7ea2hynubogjv23hodoeht3zvkarqrnn@sehlj2lzwszy>
+
+Up: [satisfiability_weighted_knowledge_compilation], [satisfiability_weighted], [obdd]
+
+Aliases: satisfiability weighted obdd
diff --git a/unambiguous_word_automaton_complementation b/unambiguous_word_automaton_complementation
@@ -2,7 +2,7 @@
[raskin2018superpolynomial], [goos2021lower]
-problem of finding assignment of maximal weight that satisfies complement of UFA https://cstheory.stackexchange.com/questions/48815/is-this-problem-on-unambiguous-finite-automata-np-complete
+[UFA_complementation_maximal_weight]
Up: [word_automaton_unambiguous], [automata_complementation]
