1
$\begingroup$

Given a boolean formula $F$ of length $n$ defined over a fixed number of variables (say 50), is it NP-complete to decide whether $F$ is satisfiable?

$\endgroup$
1
  • $\begingroup$ @Pål GD its problem just induce from when i was thinking about SAT problem, SAT problem describe $n$ variables. so i wonder if its can be fixed variables $\endgroup$
    – maplgebra
    Oct 11 at 11:58
3
$\begingroup$

If you have a fixed number of variables, then you have a fixed number of assignments $2^{|\text{vars}|}$, so there's a polynomial time algorithm for checking all possible assignments.

$\endgroup$
6
  • $\begingroup$ Though the length of boolean formula is random? $\endgroup$
    – maplgebra
    Oct 11 at 12:09
  • 2
    $\begingroup$ i think i got it, $2^{|\text{vars}|}n$, the $2^{|\text{vars}|}$ is constant. thanks! $\endgroup$
    – maplgebra
    Oct 11 at 12:11
  • $\begingroup$ In fact, linear time. $\endgroup$ Oct 11 at 18:51
  • 1
    $\begingroup$ In fact, constant time. $\endgroup$ Oct 11 at 19:53
  • 1
    $\begingroup$ @JohnColeman No, you still have to read the $n$ long formula, which takes time at least $\Omega(n)$. $\endgroup$
    – Pål GD
    Oct 11 at 20:42

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.