0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ For 3SAT you can simply brute force the solution, so that's trivially FPT. $\endgroup$ Commented Dec 18, 2023 at 9:03
  • $\begingroup$ There are $\binom{m}{k}$ sets of $k$ clauses, if that's what you are asking. $\endgroup$
    – rus9384
    Commented Dec 18, 2023 at 12:06
  • $\begingroup$ @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. $\endgroup$ Commented Dec 18, 2023 at 12:39

0

Your Answer

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