Exponential search spaces are completely typical for NP problems.

Even many "P problems" have an exponential search space. For instance an n-digit number has exp(n) many potential divisors, but there is a polynomial-in-n-time algorithm to verify primality.

"Reverse engineer" is "there is a machine that seems to find needles in haystacks quickly. It has loops of copper wire, and plugs into a wall socket. Can you copy it and build another one?"

I admit that there are some "reverse-engineering" problems that are easy.