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?