Is SAT sparse? Is this an understood problem?

Intuition suggests that SAT is definitely not sparse. For any well-formed SAT problem $\phi$, we have $(\phi \in SAT) \vee (\neg\phi \in SAT)$, and $\exists \phi : (\phi \in SAT) \wedge (\neg\phi \in SAT)$ (perhaps "many" such $\phi$ satisfy this).

The set of well-formed queries is not sparse, consider $a_1 \wedge \cdots \wedge a_n$ with each $a_n \in \{x_1, \neg x_1\}$.

But this proof is not complete since negation of a DNF and CNF and forcing canonical form changes length, and if canonical form is dropped then it is not obvious how problems relate to representations of their inverses.

• Is it known that SAT is not sparse?

• Is it possible for a dense language to reduce to a sparse language, as is supposed in Mahaney's theorem?

SAT is not sparse. For example, we have exponentially many monotone formulas per input length, and they are all satisfiable.

Regarding your second question, since most people conjecture that P≠NP, according to Mahaney's theorem those people don't expect NP-complete problems to be reducible to sparse languages.

StackExchange Computer Science Q#67607, answer score: 5