7
$\begingroup$

The reduction from SAT to Clique shows a way to construct a graph with cliques from a Boolean formula. A closer look at that reduction even yields a simple algorithm which finds a large clique in the graph from a given satisfying assignment to the variables. That mapping is bijective: each satisfying assignment is mapped to a different large clique, and the number of large cliques is the same as the number of satisfying assignments.

A reduction which preserves the number of solutions is called a parsimonious reduction (technical definition below). It is a stronger notion of reduction than the usual Karp reductions, because not all reductions have that property. NP-Completeness is usually defined in terms of Karp-reductions, but since parsimonious reductions are clearly more beautiful, it is natural to conjecture:

Conjecture: All NP-Complete problems can be reduced to one another via parsimonious reductions.

But I can't find this in the literature.

Question: Does the literature contain the conjecture that all NP-Complete languages can be reduced to eachother via parsimonious reductions?

This is different from the Bertman-Hartmanis conjecture that all NP-Complete problems can be reduced to eachother via polynomial-time invertible bijections. That conjecture is about instances of the language, whereas I talk about certificates to the NP machine. Of course the most beautiful thing would be a parsimonious bijection! References to that are greatly appreciated.

Definition If $L,K\subseteq\{0,1\}^\ast$ are languages and $f\colon\{0,1\}^\ast\to\{0,1\}^\ast$ is a reduction from $L$ to $K$, then we say that $f$ is parsimonious if there are polynomial-time nondeterministic Turing Machines $N, M$ accepting $L$ and $K$, respectively such that for all $x\in\{0,1\}^\ast$, $\#N(x)=\#M(f(x))$, where $\#N(x)$ denotes the number of certificates accepted by a non-deterministic Turing Machine on input $x$.

(The motivation for the question is that, for my thesis, I found that the reduction in the quantum Cook-Levin theorem is parsimonious. Beautiful! I want to conjecture that all quantum NP complete problems have parsimonious reductions, so I am looking for the classical reference)

Improve this question
$\endgroup$
12
  • $\begingroup$ Exercise 2.13 in SANJEEV ARORA's book (Computational Complexity) asks to "Prove that the reduction from every NP-language L to SAT presented in the proof of Lemma 2.11 can be made parsimonious." $\endgroup$
    – fade2black
    Jul 14, 2017 at 21:18
  • $\begingroup$ @fade2black That is a result they use in the book a lot later on. The conjecture is that there is a parsimonious reduction from SAT to other languages, too, which is not obvious. But good find! This is an essential fact to remember when proving almost all other completeness properties of other classes. $\endgroup$
    – Lieuwe Vinkhuijzen
    Jul 14, 2017 at 21:22
  • $\begingroup$ I am pretty sure this is an open problem, though it is not discussed much (at least not in this form). The connection to counting problems appears more often. Perhaps you will find the discussions in these posts interesting cstheory.stackexchange.com/questions/16119/… cs.stackexchange.com/questions/3295/… $\endgroup$
    – Ariel
    Jul 14, 2017 at 22:19
  • $\begingroup$ Well, example is not good, because two given problems are one-by-one reducible to each other (that's why max clique is in SNP). $\endgroup$
    – rus9384
    Jul 14, 2017 at 22:43
  • $\begingroup$ @fade2black, existence of parsimonious reduction from any problem in NP to a problem from SNP does not imply the opposite statement. $\endgroup$
    – rus9384
    Jul 14, 2017 at 22:47

2 Answers 2

Reset to default
2
$\begingroup$

Yes, it is well known conjecture. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).

Improve this answer
$\endgroup$
0
1
$\begingroup$
  1. This is an easy consequence of Berman-Hartmanis.

Assuming that Berman-Hartmanis holds, for every pair of $NP$-complete problems $L, K$, we show that it is possible to parsimoniously reduce $L$ to $K$. In fact, every poly-time invertible bijective reduction will be parsimonious then.

Indeed, fix some NTM $N$ that decides $L$ and a poly-time invertible bijective reduction $f$ from $L$ to $K$ (which always exists by Berman-Hartmanis), consider the following NTM $M$ that decides $K$: on an input $y\in\Sigma^*$, compute the preimage $x=f^{-1}(y)$ (which is poly-time computable since $f$ is poly-time invertible by assumption), then run $N(x)$.

Clearly, $M$ is a non-deterministic polynomial-time Turing machine accepting $K$. And, for every $x\in L$, denote $y=f(x)$, we have that every certificate $c$ for $x$ according to $N$ is also a certificate for $y$ according to $M$, and vice versa. So, $\#N(x)=\#M(y)$. For every $x\not\in L$, $\#N(x)=\#M(y)=0$.

  1. If $NP=UP$ (which is considered unlikely) including the subcase of $NP=P$

Every reduction is then parsimonious without the requirement of being poly-time invertible (or even being bijective) at all.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ What if, for example, $L$ is SAT and $K$ is NAE-3SAT? How can SAT be reduced parsimoniously to NAE-3SAT? In particular, for any instance of SAT with an odd number of solutions, there is no instance of NAE-3SAT with the same number of solutions, because every instance of NAE-3SAT has an even number of solutions (for every assignment that NAE-satisfies a given formula, so does the complement of that assignment)? What am I missing? $\endgroup$
    – Neal Young
    Jun 4, 2020 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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