We prove that decision trees exhibit the "approximate fingerprint" property, and therefore are not polynomially learnable using only equivalence queries. A slight modification of the proof extends this result to several other representation classes of boolean concepts which have been studied in computational learning theory.