On the hardness of the minimum height decision tree problem
Given a set of objects O and a set of tests T, the abstract decision tree problem (DTP) is to construct a tree with minimum height that completely identifies the objects of O, by using the tests of T . No algorithm with a good approximation ratio is known to solve this problem. We give a theoretical support for this fact by showing that DTP does not admit an o(log?n) o ( log ? n ) -approximation algorithm unless P=NP.
decision trees algorithmical approximation computational complexity