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

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

1 Answer 1


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

Thus, your algorithm runs in polynomial time

  • $\begingroup$ this is just what I was looking for, thank you $\endgroup$
    – zython
    Sep 2, 2018 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.