Decision trees have approximate fingerprints
Víctor Angel Lavín Puente, Vijay Raghavan · 1996
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.