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:

1. the initial space of possibilities is exponential in the size of the input,
2. the search space decreases monotonically as we read the input,
3. 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?

• I don't understand what properties 2 and 3 mean; can you elaborate? If you have read the entire input, then the search space is narrowed down to only correct answers. – usul Jan 18 '13 at 16:43

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.

No, it completely depends on how much structure your space has. Suppose you want to search for an element in an exponentially large sorted list. Using binary search you only need to look at a polynomial number of elements.

For some special kinds of spaces you can even search infinitely many elements using only finite time. See for example here how to do that in Haskell.

So unless I misunderstand what you mean with "the search space is getting smaller as we read the input" (i.e. how much computational ressources are you allowed to expend to make the search space smaller?) the answer is no, having an exponential (or even larger) search space is not enough to show a lower bound.

• What do you mean by "exponentially large sorted list"? The OP means the search space is exponential in the size of the input, which in this case is the size of the sorted list. – Paresh Jan 18 '13 at 9:56
• I mean you have a fixed list of size 2^n in which you look for words of length n. – adrianN Jan 18 '13 at 11:45

The short answer is No. Here is the counter-example:

Problem P: Find the shortest path from source $s$ to target $t$ in a undirected graph $G = (V, E)$.

Input: Initially, the input is |V|, and the complete graph of |V| vertices is assumed. Subsequently, the input consists of edges that need to be removed from this original complete graph. (This roundabout input is to cater to your need of search space decreasing monotonically as we read the input).

Search space: All possible paths from $s$ to $t$ in $G$.

The number of paths from $s$ to $t$ grows faster than exponential in |V| (it is a factorial function). But the shortest path can be found in polynomial time, even in the worst case.

In other words, exponential search space does not imply that no polynomial time algorithm is possible.