3
$\begingroup$

A binary decision tree (DT) is a binary tree whose internal nodes are labelled by boolean variables (with repetitions), and whose leaves are labelled either $0$ or $1$. The size of a decision tree is the number of branches (or equivalently the number of leaves).

A DT determines a unique Boolean function of the variables labelling the internal nodes: given an assignment of these variables, start at the root of the tree and take the left branch if the label is assigned $0$ and the right branch otherwise, and repeat until a leaf is reached; the value of the function is the label of the leaf. Any boolean function $f\colon \{0,1\}^n\to\{0,1\}$ can be represented by a DT with size $2^n$ (a complete tree where the $i^\text{th}$ level of internal nodes is labelled by variable $x_i$).


Question: Is the class of languages recognisable by a family of polynomial-size decision trees known to be related to a ''natural'' class of single-output boolean circuits (e.g. NC$^0$, TC$^0$...)?

I am hoping for something analogous to Barrington's theorem [Bar89] for branching programs (which can be seen as an extension of DTs where ''tree'' is replaced by ''DAG'').

The class of decision problems solvable by a family of polynomial-size, constant-width ($\geq 5$) branching programs is exactly (non-uniform) NC$^1$.

However, the existence of strong learning algorithms for DTs [BLQT21] leads me to believe I'm looking for far less expressive classes.


[Bar89] D. A. M. Barrington. Bounded-width polynomial-size branching programs can recognize exactly those languages in NC1, Journal of Computer and System Sciences 38:150-164, 1989.

[BLQT21] Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan: Properly learning decision trees in almost polynomial time. CoRR abs/2109.00637 (2021).

$\endgroup$

1 Answer 1

2
$\begingroup$

This is not an exact characterization, but the class of languages recognizable by poly-size DT is included in $\mathrm{AC}^0$, specifically within its second level: that is, any DT can be converted to a polynomially larger CNF and DNF. To see this, take $$\bigvee_i\bigwedge_jp_{i,j},$$ where $i$ runs over all accepting leaves of the DT, and for each $i$, $p_{i,j}$ enumerates literals corresponding to the decisions made on the path from the root to $i$.

$\endgroup$
2
  • $\begingroup$ Interestingly, we can further narrow down the class: every function admitting a poly-size DT admits both a poly-size CNF and a poly-size DNF (as you wrote), but the converse is not true, as shown by [JRSW99]. [JRSW99] S. Jukna, A. Razborov, P. Savický, I. Wegener, "On P versus NP$\cap$co-NP for decision trees and read-once branching programs" (dx.doi.org/10.1007/s000370050005) $\endgroup$
    – integrator
    Jan 4, 2022 at 16:10
  • $\begingroup$ Yes, that’s why I write this is not an exact characterization in the answer. $\endgroup$ Jan 25, 2022 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.