# The parameterized complexity of Weighted-CNF-SAT parameterized by the number of clauses

What is the parameterized complexity of Weighted-CNF-SAT, when parameterized by the number of clauses?

Input: A CNF formula $$\phi$$ with $$m$$ clauses and $$n$$ variables, and an integer $$k$$.

Parameter: $$m$$

Output: Does there exist an assignment to $$\phi$$ with hamming weight $$k$$?

When this problem is parameterized by $$k$$ it is known to be $$W[2]$$-Complete.

Is there a known result on this complexity when parameterized by m?

Are there any similar results? Perhaps - CNF-SAT, parameterized by the number of clauses, or Weighted-CNF-3SAT, parameterized by the number of clauses?

• For 3SAT you can simply brute force the solution, so that's trivially FPT. Commented Dec 18, 2023 at 9:03
• There are $\binom{m}{k}$ sets of $k$ clauses, if that's what you are asking. Commented Dec 18, 2023 at 12:06
• @PålGD Yes, you are right! Is there a solution though for the non-restricted CNF case? It does not seem to be FPT. However, I wasn't able to prove para-NP/W[1]/W[2] hardness either. Commented Dec 18, 2023 at 12:39