2
$\begingroup$

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.

$\endgroup$
  • $\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 '18 at 13:51
  • $\begingroup$ What do you mean by a combination of input variables satisfying the formula? $\endgroup$ – David Richerby Sep 2 '18 at 20:54
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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