commit 25092643561feca140e29ec51c9e5fe07f4bcfcd
parent d3efee04449f0f689efe8048f488155cda88d823
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 11 Dec 2025 20:53:11 +0100
commit with codex
Diffstat:
5 files changed, 15 insertions(+), 0 deletions(-)
diff --git a/circuit_lower_bound b/circuit_lower_bound
@@ -2,4 +2,11 @@
best known bound on an explicit function: [find2015better], (3+1/86)n - o(n) lower bound on the size of [boolean_circuit] for a [boolean_function]
+- [SDNNF_lower_bounds]
+- [DNNF_lower_bounds]
+- [dSDNNF_lower_bounds]
+- [dDNNF_lower_bounds]
+
Up: [circuit_size]
+
+Aliases: circuit lower bounds
diff --git a/ddnnf b/ddnnf
@@ -4,6 +4,8 @@
[circuit_equivalence_problem]: [circuit_equivalence_dDNNFs]
+- [dDNNF_lower_bounds]
+
Up: [knowledge_compilation_classes], [dd]
See also: [dnnf], [decision_dnnf], [uobdd], [times_uplus_circuit]
diff --git a/dnnf b/dnnf
@@ -14,6 +14,8 @@ Special cases:
Compilation of DNNFs to [conjunctive_normal_form] cannot be done tractably because DNNFs include [DNFs]
+- [DNNF_lower_bounds]
+
See also: [ddnnf], [decision_dnnf], [times_cup_circuit]
Up: [knowledge_compilation_classes]
diff --git a/dsdnnf b/dsdnnf
@@ -4,6 +4,8 @@
not closed under [complementation], cf [vinallsmeeth2024structured] by [harry]
+- [dSDNNF_lower_bounds]
+
Up: [knowledge_compilation_classes], [ddnnf], [sdnnf]
Aliases: dSDNNFs, d_SDNNFs, d_SDNNF
diff --git a/sdnnf b/sdnnf
@@ -2,6 +2,8 @@
like [DNNFs] but [structured]
+- [SDNNF_lower_bounds]
+
Up: [knowledge_compilation_classes], [dnnf], [structuredness]
Aliases: SDNNFs
