Variation de max 3-SAT

Question

Supposons que nous ayons un 3CNF, et nous voulons savoir si K Clauses de ce 3CNF peut être satisfaite (k étant un nombre naturel)?

J'essaie de penser à un algorithme efficace pour résoudre ce problème. Il s'agit d'une sorte de variation du 3-SAT MAX, mais avec un k fixe. Si nous avons M clauses, la vérification naïvement obtiendrait des comparaisons $ binom {m} {k} $, mais cela semble factoriel (si nous approximations avec la complexité de la formule, exponentielle) de Sterling.

Quel pourrait être un moyen efficace de vérifier cela? J'ai dû louper quelque chose. Merci.