Search spaces and computation time
No, in general you can't assume that an exponential search space requires exponential time to search. Linear programming generally has an exponential search space but can be done in (weakly) polynomial time.