Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
Thank you very much, great explanation! –  tam Feb 14 '13 at 17:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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