In fact, the essence of decompilation is a NP-Complete problem: Graph Isomorphism.

So far, our decompilers are just greedy scheme to approximate the original expressions as best as possible by treating each instruction as a tree then as a graph, but still even a single assignment could cause the entire outcome of the code to change a lot, let alone to correctly recognizing heavily optimized procedures.

Edit: Wiki said it is NP-Complete but I was pretty sketchy about it. I think the better wording should be "at least NP"