Satisfiability with exponential families

Fix a set S⊆{0,1}∗ of exponential size, e.g. |S∩{0,1}^n|∈Ω(α^n),α>1. The S-SAT problem asks whether a propositional formula F over variables v_1, ..., v_n has a satisfying assignment (v_1,…,v_n)∈{0,1}^n∩S. Our interest is in determining the complexity of S-SAT. We prove that S-SAT is NP-complete for all context-free sets S. Furthermore, we show that if S-SAT is in P for some exponential S, then SAT and all problems in NP have polynomial circuits. This strongly indicates that satisfiability with exponential families is a hard problem. However, we also give an example of an exponential set S for which the S-SAT problem is not NP-hard, provided P≠NP