Definition of Strongly Parsimonious Reduction

Question

There is a well known definition of parsimonious reduction.

The standard definition of parsimonious reduction is very intuitive. It simply means that the two problem have the same number of solutions, when on input of one of them we applied function $f$.

We say there is a parsimonious reduction from #A to #B if there is a polynomial time transformation $f$ such that for all $x$, $|\{y,(x, y) \in A\}| = |\{z : (f(x), z) \in B\}|$.

I am interested in definition of strongly parsimonious reduction.

The only definition I found:

"Strongly parsimonious reduction of $R'$ to $R$ is a parsimonious reduction $g$ that is coupled with an efficiently computable 1-1 mapping of pairs $(g(x), y) \in R$ to pairs $(x, h(x, y)) \in R'$ (i.e., $h$ is efficiently computable and $h(x, ·)$ is a 1-1 mapping of $R(g(x))$ to $R'(x)$). For technical reasons, we also assume that $|g(x)| ≥ |x|$ for every $x$."

The problem is I simply don't understand what this definition means. I tried to separate it to smaller block, but so far with no success. According to the definition there are two function $g(x)$ and $h(x,y)$ are they are applied simultaneously to two different problem $R$ and $R'$. How the usages of two function can be explained. What is the difference between two reduction, parsimonious reduction and strongly parsimonious reduction.

I would appreciate any help in understanding the definition of strongly parsimonious reduction.

Answer 1

A search problem is defined by a relation like $R$. The task is given an input $x$ find a solution $y$ s.t. $R(x,y)$ is true.

A counting problem is defined as counting the number of solutions of a search problem, i.e. given an input $x$ we want to compute the number of $y$s s.t. $R(x,y)$ holds. The counting problem associated with search problem $R$ is denoted by $\#R: \Sigma^* \to \mathbb{N}$, $x \mapsto \#y: R(x,y)$.

A parsimonious reduction $f$ between counting problems only needs to preserve the number of $y$s, i.e. for all $x$,

$$\#y:R(x,y) = \#z:S(f(x),z)$$

A strongly parsimonious reduction has an the extra property that you mentioned. The meaning of the property should become clear if you look at it in the following way:

Assume that we want to use the search problem $S$ to solve the search problem $R$.
On an input $x$ for $R$, we first compute $g(x)$ which is an input for $S$.
Then we use $S$ to find an $S$-solution $y$ for $g(x)$, i.e. $(g(x),y)\in S$.
Finally we compute $h(x,y)$ to obtain an $R$-solution for $x$.

Now if we want to preserve the number of solutions between these two search problems, we can make sure that for every $x$, the function $h(x,\cdot)$ that computes an $R$-solution for $x$ from an $S$-solution $y$ for $g(x)$ is a bijection.

The difference should be clear now: not only the number of $R$-solutions for $x$ and $S$-solutions for $g(x)$ are equal, there is an efficient bijection between those solutions.