Proving special case of SAT is in P Let SAT-100 be the following problem:

Input: Any boolean logic formula

Output: True if there exists a combination of exactly 100 input variables that satisfy the formula.

This is the description of a problem that is apparently in $P$. (old exam question)

I have tried to design an algorithm but I got stuck, so here it goes:

Input: boolean logic formula F
    If(count(variables in F)) &lt; 100:
       return false
    else
        # try all combinations of input variables


And here is the problem: building and evaluating all combinations of input variables can't seem to be polynomial because:

$$ { n \choose 100} = \frac{n! }{100!  \cdot (n-100)!} \in \mathcal{O}(n!)
$$

and this nasty factorial can't be bounded with any polynomial that I know of.

I don't think  the exam is wrong, so I must have overlooked something.
Note that
$$\frac{n!}{(n-100)!100!}&lt;\frac{n!}{(n-100)!}= n \cdot (n-1)\cdot \ldots \cdot (n-99)&lt; n^{100}.$$

Thus, your algorithm runs in polynomial time