Search spaces and computation time This question follows on previous questions (1), (2), where we define an initial space of possibilities and reason about how a solution is chosen from that.

Consider a problem P where we are given:


the initial space of possibilities is exponential in the size of the input,
the search space decreases monotonically as we read the input, 
for the algorithm that correctly computes P and has the minimum worst-case performance, the search space is still exponential in the size of the input even after the final input is read.


Can we conclude that P requires exponential time? If not, what would a polynomial-time counterexample look like?
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.