optimal decision tree np-hard Reading Elements of Statistical Learning and it says that decision trees are often constructed using greedy algorithms because it is computationally infeasible to create an optimal decision tree. There is a proof here but it relies upon several other topics (exact covers, 3-dimensional matching), so I was wondering first if anyone has an intuitive explanation for this.
 A: Complexity theorists have identified a class of problems called "NP-hard" which are "intractable", meaning that no one has figured out how to solve them efficiently, despite much effort. 
Suppose you know some problem A which you know is in this class of "NP-hard" problems. And suppose you can solve it by converting it to an instance of finding the optimal decision tree. Then, you know that finding an optimal decision tree must be very hard, because if it was easy, you could just solve problem A by converting it to an instance of the optimal decision tree problem and solving that. This is called a reduction.
For example, you can convert the problem of finding the maximum number in a list to the problem of sorting a list, since you can always sort the list, and then return the last number in the sorted list as your answer. You've now shown sorting is at least as hard as finding the maximum number, or analogously, that finding the optimal decision tree is as hard as problem A.
In the paper you linked, problem A goes by the name "exact cover by 3-sets". Then, you might ask how complexity theorists proved EC3 or any of the NP-hard problems are actually intractable. Actually there is no such proof, but the conjecture that NP-hard problems cannot be solved efficiently is called P $\neq$ NP.
(This answer misses out on a lot of complexity theory details for the sake of intuition, so it's not completely rigorous.)
