Language $L$ is sparse if there exists a polynomial $p$ such that $|L ∩ \{0,1\}^n| ≤ p(n)$. Thus, if there are at most polynomial number of strings for each length $n$ in the set $S$ (where $S$ represents the language $L$), the set $S$ is a sparse set.

Mahaney's theorem states that if an NP-complete language is Karp-reducible to a sparse language then P=NP.

As I understand, the $S$ would consist strings of form $\langle Q_i, x_i\rangle$ where $Q_i$ is a 3SAT instance, and $x_i$ is one of its variables. Thus, for all $k$ inputs accepted by any $Q_i$, we would have $k$ strings of the form above (one for each accepted input $x_i$). And the length would be the size of the resultant string for $\langle Q_i, x_i \rangle$.

If my understanding is correct, can someone help with a small example how to convert a SAT problem into equivalent string. The inputs $x_i$'s would be in binary already, but not clear how to get the string equivalent to $\langle Q_i, x_i\rangle$?

  • 1
    $\begingroup$ I'm not sure I follow. We don't think that SAT is Karp-reducible to a sparse language, and in particular we don't know how such a hypothetical sparse language would look like. $\endgroup$ – Yuval Filmus Jul 1 '17 at 14:31
  • $\begingroup$ Of course other wise P=NP :). I meant an example of converting a single instance of SAT to a equivalent language in binary set S.I know reductions b/w NPC Problems, but not sure how to convert SAT into an equivalent language. $\endgroup$ – J.Doe Jul 1 '17 at 14:35
  • $\begingroup$ It seems you are referring to a particular proof of Mahaney's theorem. Your question doesn't make too much sense outside of this context. Perhaps you could add a link to the particular proof, and which step exactly you are having troubles with. $\endgroup$ – Yuval Filmus Jul 1 '17 at 14:40
  • $\begingroup$ cs.umd.edu/~jkatz/complexity/f05/lecture6.pdf I am using these notes. The question was in 2 parts. (1) If my generic understanding of the Mahaney's Theorem is correct in general. The notes use a language LSAT and they mention if LSAT is Karp reducible to Sparse Language P=NP. (2) How to convert a concrete instance of a SAT problem to a language problem (a reduction or encoding process). I am not clear regarding this. $\endgroup$ – J.Doe Jul 1 '17 at 15:15
  • $\begingroup$ I still can't understand your second question. A Karp reduction from a language $L_1$ to a language $L_2$ is a polytime function $f$ such that $x \in L_1$ iff $f(x) \in L_2$. Is this the sense in which you mean "convert a concrete instance of a SAT problem to a language problem"? If so, what are $L_1,L_2$? $\endgroup$ – Yuval Filmus Jul 1 '17 at 15:32

Your Answer

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

Browse other questions tagged or ask your own question.