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.

  • SAT is not sparse. For example $(x_1 \vee \neg x_1) \vee (anything)$ is in SAT.
  • If SAT reduces to a sparse language (which is unexpected because it would imply P = NP by Mahaney), the reduction would necessarily include many collisions.
  • If P = NP, SAT reduces to the sparse language $\{1\} \subset \{0,1\}^n$.
  • In general, reductions can have collisions. For instance, any reduction from a canonical form such as CNF or DNF has collisions for any two representations of a formula with the same canonical form.
  • 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.
  • If P = NP, then there are many sparse languages that are NP complete. In fact any sparse language in P would be NP complete in this case.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.