- INSTANCE:
Finite set
*X*of objects, collection of binary tests . - SOLUTION:
A decision tree
*t*for*X*using the tests in*T*, where a decision tree is a binary tree in which each non-leaf vertex is labelled by a test from*T*, each leaf is labelled by an object from*X*, the edge from a non-leaf vertex to its left son is labelled 0 and the one to its right son is labelled 1, and, if is the sequence of vertex and edge labels on the path from the root to a leaf labelled by , then*x*is the unique object for which for all*j*, . - MEASURE:
Number of leaves of
*t*.

*Bad News:*APX-hard [233].*Comment:*Not approximable within unless [233].*Garey and Johnson:*MS15