# CNF satisfiability with a bound on number of clauses

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?

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.