What are good simple partitioning algorithms?

I have complete knowledge of how a set of input variables are transformed into output variables, and want to derive a small/smallest decision tree for deciding output values from input values. The matching must be accurate.

I’ve a feeling that smallest = NP, but there must be something that can give me small in P.

Just try a handful of combinations and use a standard BDD algorithm? Some sort of backtracking algorithm?