A parsimonious reduction is a transformation from one problem to another problem such that the number of solutions is preserved. More precisely, a parsimonious reduction is a typical (polynomial time) many-one reduction that additionally does not increase the number of solutions in the transformed instance. Parsimonious reductions are used to prove hardness for counting complexity classes, such as $\#P$.
Definitions
For a formal reductions of parsimonious reductions, we first define a computational problem as a tuple of a language with a corresponding solution set, which include the certificates encoded as strings of 0s and 1s.
Definition (Computational problem) A computational problem $\Pi$ is a tuple $(\mathcal{I},\mathcal{S})$, such that
- $\mathcal{I} \subseteq \{0,1\}^*$ is a language. We call $\mathcal{I}$ the set of instances of $\Pi$.
- To each instance $I \in \mathcal{I}$, there is some (potentially empty) set $\mathcal{S}(I) \subseteq \{0,1\}^*$, which we call the solution set associated to the instance $I$.
We can distinguish between two flavors of parsimonious reductions: weak and strong. While weak parsimonious reductions require the number of solutions to be equal, strongly parsimonious require a bijective mapping between the solutions of the instances, which is computable in polynomial time. Because a bijective mapping between two finite sets imply that the sets have equal size, strongly parsimonious reductions are always weakly parsimonious. We begin with the definition of weakly parsimonious reductions.
Definition (Weakly Parsimonious Reduction) Let $\Pi = (\mathcal{I},\mathcal{S})$ and $\Pi' = (\mathcal{I}',\mathcal{S}')$ be two computational problems. We say that there is a weakly parsimonious reduction from $\Pi$ to $\Pi'$, and write $\Pi \leq_{WPR} \Pi'$, if
- There exists a function $g: \{0,1\}^* \rightarrow \{0,1\}^*$ computable in polynomial time in the input size $|I|$, such that $I$ is a Yes-instance iff $g(I)$ is a Yes-instance (i.e. $\mathcal{S}(I) \neq \emptyset$ iff $\mathcal{S}'(g(I)) = \emptyset$).
- The number of solutions of $I$, $|\mathcal{S}(I)|$, is equal to the number of solutions of $g(I)$, $|\mathcal{S}'(g(I))|$.
On the other hand, strongly parsimonious reductions are defined as follows.
Definition (Strongly Parsimonious Reduction) Let $\Pi = (\mathcal{I},\mathcal{S})$ and $\Pi' = (\mathcal{I}',\mathcal{S}')$ be two computational problems. We say that there is a weakly parsimonious reduction from $\Pi$ to $\Pi'$, and write $\Pi \leq_{WPR} \Pi'$, if
- There exists a function $g: \{0,1\}^* \rightarrow \{0,1\}^*$ computable in polynomial time in the input size $|I|$, such that $I$ is a Yes-instance iff $g(I)$ is a Yes-instance (i.e. $\mathcal{S}(I) \neq \emptyset$ iff $\mathcal{S}'(g(I)) = \emptyset$).
- There exist functions $(p_I)_{I \in \mathcal{I}}$ computable in polynomial time in $|I|$ such that for all instances $I \in \mathcal{I}$, $p_I: \mathcal{S} \rightarrow \mathcal{S}'(g(I))$ is a bijective function from the solution set of instance $I$ to the solution set of $g(I)$.
Applications
Parsimonious reductions are used to show hardness for counting complexity classes. Among these are
- $\#P$, the class of problems, for which to count the number of accepting paths of a non-deterministic polynomial time Turing machine. The canonical complete problems are $\#$SAT, i.e. counting the number satisfying assignments of a Boolean formula, and 01-PERMANENT, i.e. computing the permanent of a 01-matrix.
- $\#W[t]$, which is the analogue of $\#P$ in the parameterized world. Here not polynomial many-one parsimonious reductions are used, but parsimonious FPT-reductions. The canonical complete problem is $\#$Weighted-Weft-$t$-Circuit-SAT.