3
$\begingroup$

Consider the CNF-sat problem with n literals and k clauses. If k scales linearly in n, we get np-completeness (e.g., 3-sat where each literal appears at most 4 times). Do we still get np-completeness if we restrict attention to problem instances where k scales sublinearly in n? For this question, I am not requiring clauses to consist of 3 literals, but I still need the formula to be CNF.

More generally, how does complexity scale (for known algorithms) with k?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Here is an $n^{O(k)}$-time SAT algorithm: try all (at most $n^k$) ways how to select one literal from each clause, and accept whenever the selection is such that it does not include any contradictory pair (i.e., a literal and its negation). So, if $k$ is substantially smaller than $n$, you get a subexponential algorithm, and you should not be able to prove NP-completeness of such a restricted problem.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.