# NP-completeness of satisfiability of formula over 50 variables

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?

• @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 Oct 11 at 11:58

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.
• i think i got it, $2^{|\text{vars}|}n$, the $2^{|\text{vars}|}$ is constant. thanks! Oct 11 at 12:11
• @JohnColeman No, you still have to read the $n$ long formula, which takes time at least $\Omega(n)$. Oct 11 at 20:42