title: Perfect decision tree classification
body: <p>Imagine that the universe of all known mappings between the values of a set of variables V and a set of tag names T (classification labels) was known. Further, assume that the total space of unique variable value combinations is large (> 100B points), the size of the tag set is relatively small (thousands of elements) and the number of variables is very small (4-10). </p>
  
  <p>What is a algorithm for building a classifier function that provides a perfect mapping (matching the a priori knowledge with no false positives or false negatives) from variable values to labels with the following space and time complexity goals:</p>
  
  <ul>
  <li>Time complexity lower than O(|V|*log|T|)</li>
  <li>Space complexity less than O(|V|<sup>k</sup>), k &le; <em>e</em></li>
  </ul>
  
  <p>Or, rephrased as a decision tree problem:</p>
  
  <ol>
  <li>How can a decision tree algorithm be tuned to create a perfect mapping?</li>
  <li>How can the training data be represented efficiently to guarantee that?</li>
  </ol>