There are parsimonious reductions between all NP-Complete problems: Well-known conjecture?

Question

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)

Answer 1

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).

Answer 2

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$.

2. 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.