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?