I am wondering what is the complexity status of 3-SAT when the number of variables is small compare to the number of clauses.
Let n be the number of variables plus the number of clauses. It is clear that if the number of variables is a constant, then we can brutally solve the problem. It is actually still the case when the number of variable is a O(log n). Does it become NP-c as soon as the number of variables is a asymptotically larger then log n?
Thanks!