commit 0822f6a646bb2245ff4080684bd50ebb79b46cb0
parent 2683aed37f9ff236dd6f8a64ca09a6e3d3ef0b56
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 15 Apr 2026 18:16:27 +0200
commit with codex
Diffstat:
3 files changed, 15 insertions(+), 4 deletions(-)
diff --git a/circuit_value_problem b/circuit_value_problem
@@ -1,7 +1,11 @@
# Circuit value problem
+https://en.wikipedia.org/wiki/Circuit_value_problem
+
Given a [Boolean_circuit] with Boolean values on the gates, and a [gate], decide if that [gate] evaluates to [true]
+It is [P_complete]
+
Up: [decision_problem] on [circuit]
-See also: [formula_value_problem]
+See also: [formula_value_problem], [circuit_satisfiability_problem]
diff --git a/formula_value_problem b/formula_value_problem
@@ -0,0 +1,9 @@
+# Formula value problem
+
+Given a [Boolean_formula] with Boolean values for the variables, decide if it evaluates to [true]
+
+It is [NC1_complete]
+
+See also: [circuit_value_problem], [tree_evaluation_problem], [formula_satisfiability_problem]
+
+Up: [decision_problem], [boolean_formula]
diff --git a/tree_evaluation_problem b/tree_evaluation_problem
@@ -2,7 +2,7 @@
You have a [tree] and you want to evaluate a [bottom_up_nondeterministic_tree_automaton] on the tree, in a [nonuniform] sense where each [node] is labeled by the transition function
-Covers in particular the evaluation of [Boolean_formulas] and the acceptance of a fixed [tree_automaton]
+Covers in particular the [formula_value_problem] and the acceptance of a fixed [tree_automaton]
Sometimes considered specifically on [complete_binary_trees] and on functions at the nodes given as input.
@@ -12,5 +12,3 @@ It is in O(log n log log n), cf [cook2023tree] and [goldreich2024cook]
Up: [computational_problem] on [tree]
Aliases: TreeEval, tree evaluation
-
-See also: [formula_value_problem]
