- a set of $n!$ input possibilities
- a goal space of only one element consisting of the one correct sorted sequence
We then arrived at a generalized argument which I'll alter slightly and call A:
- Define a space of input possibilities
- Define the goal space, a subset of the input space
- Reason about constraints in order to set a lower bound
Three Questions: given that there are quadratic algorithms for sorting,
- Can we conclude for the quadratic sorting algorithms, where we have an input space of $n!$ input possibilities and roughly $n^2$ steps, that there are $O(n!/n^2)$ possibilities removed from the search space per step on average?
- Let's say we're given a problem formalizable in the form of argument A above where the input space is exponential in terms of the size of the input, $O(2^n)$, and the problem is solvable in polynomial time, $O(n^c)$, for some constant $c$. Can we conclude there are $O(2^n/n^c)$ possibilities removed from the search space per step on average?
- Can we at least conclude that a $O(2^n)$ problem cannot be solved in polynomial time by removing one element from the input space per step?