Another way to put this question is, if a boolean satisfiability solution had an efficiency of O(2^n), what would be considered n?
It seems like it could be the number of variables in the expression, or the number of clauses in the expression, or some third option I'm not thinking of.