# 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 $(x_1 \vee \neg x_1) \vee (anything)$ is in SAT.
• If P = NP, SAT reduces to the sparse language $\{1\} \subset \{0,1\}^n$.
• P contains many dense languages, such as "strings with an even number of 1s" or, even just "all strings." These all reduce to $\{1\} \subset \{0,1\}^n$.
• NP problems that are not NP hard can reduce to sparse languages. For instance, every P $\subset$ NP problem does.