tree_evaluation_problem (600B)
1 # Tree evaluation problem 2 3 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 4 5 Covers in particular the [formula_value_problem] and the acceptance of a fixed [tree_automaton] 6 7 Sometimes considered specifically on [complete_binary_trees] and on functions at the nodes given as input. 8 9 It is in O(log n log log n), cf [cook2023tree] and [goldreich2024cook] 10 => leading to [williams2025simulating] 11 12 Up: [computational_problem] on [tree] 13 14 Aliases: TreeEval, tree evaluation