Running time for algorithms

Question

Suppose i have a set $\{1,2,...,n\}$ and i know that the solution to my problem is a subset $S \subseteq \{1,2,...,n\}$. Clearly trying out all subsets in an exhaustive approach is far too time consuming in a worst case setting. However how would this change if say i had a bound on the size of my subset? Perhaps $|S|\leq r$ where $r$ is a constant. Does anybody know how this would affect running time if $n \rightarrow \infty$? Is there a minimum value of $r$ for which running time is still polynomial?

Answer 1

For a fixed $r$, if you test all subsets with $|S| \le r$, then you are testing $$ \sum_{i=0}^r {n \choose i} = O(n^r) $$ subsets, which is polynomial. However, if you were to attempt to test all subsets up to size, say $r_n$, where $r_n$ varies with $n$ and is arbitrarily high, then the runtime would be larger than $\theta(n^{r_N})$ for any particular $r_N$, so the runtime would not be polynomial. In other words, if you are just testing all subsets, the only way you can get polynomial runtime is if the size of the subset is bounded by a constant $r$.

As you have probably realized, your problem is in NP: you want to know if there exists a subset of $\{1,2,\ldots,n\}$ which has a certain property, and given a subset it can be checked whether it has the desired property in polynomial time. So if P = NP then there is a polynomial time solution to your problem that somehow is more efficient than checking all subsets.