# How hard is it to compute an approximately optimal non-greedy CART tree?

The question itself is closer to the bottom of this post, and
is formulated without any rerefence to the term "CART".

Motivation:
In traditional CART (Classification and Regression Trees), one simply chooses the locally-optimal question at each step. $\:$ However, it is not obviously the case that doing so produces a
globally-optimal tree of questions. $\:$ In formalizing this problem, attributes with a canonical
total order do not pose any issues; the nodes are allowed order-comparisons and nothing else.
The two issues I see are attributes without a canonical total order (categorical attributes), and what trees are allowed. $\:$ One possibility for categorical attributes is to allow the nodes to apply a circuit of bounded size; however, the feasibility or lack thereof in that case is likely to depend on cryptographic assumptions. $\:$ Instead, I will require that the input come with an explicit list of the tests that a single node is allowed to apply to a given categorical attribute. $\:$ Since the number of values of each totally-ordered attribute is at most the number of data-points, one can in that case convert an instance so that all attributes will be categorical. $\:$ After doing that, the number of allowed tests per attribute is at most the total number of allowed tests, so one can convert an instance so that all attributes are binary (with the bits given by the responses to each of the allowed tests), and one no longer needs to worry about what tests are allowed.
The other issue was what trees are allowed. $\:$ Since I have no idea how one would weight
depth vs. number of nodes, I will keep things simple and require that the trees be perfect.

Actual Question: $\:$ Is there an additive-error PTAS for the following minimization problem?

Inputs: $\:$ a positive integer S that is given in unary, a positive integer n,
and a non-empty list of binary vectors whose lengths are all n+1,

Well-Formed Outputs: $\:$ a perfect binary tree of depth d that has each non-leaf node labelled with an element of {0,1,2,3,...,n-2,n-1}, where d is the greatest integer that satisfies 2^d ≤ S

Value of a Well-Formed Output: $\:$ the conditional entropy of the last entry of V (which is V[n])
given the leaf-node that one ends at when going out from the root along the edges indicated
by V[current_node's_label], where V is chosen uniformly from the list of vectors in the input