# 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)) < 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.

• Hint: how many input variable combinations are there and how long does it take to check if each one satisfies the formula or not? – badroit Sep 2 '18 at 13:51
• What do you mean by a combination of input variables satisfying the formula? – David Richerby Sep 2 '18 at 20:54

Note that $$\frac{n!}{(n-100)!100!}<\frac{n!}{(n-100)!}= n \cdot (n-1)\cdot \ldots \cdot (n-99)< n^{100}.$$