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 definition 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$.
There are several notions on parsimonious reductions. In general, a parsimonious reduction guarantees that the number of solutions of the first problem is in relation to the number of solutions of the second problem, which is typically referred to as weakly parsimonious. I.e. there is a function $f: \mathbb{N} \rightarrow \mathbb{N}$ mapping the number of solutions $n$ in the first problem to a number of solutions $f(n)$ in the second problem. The most strict definition is the following of strongly parsimonious reductions, which require a bijective mapping between the solutions of the instances, which is computable in polynomial time. Accordingly, strongly parsimonious reductions are also weakly parsimonious.
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 strongly parsimonious reduction from $\Pi$ to $\Pi'$, and write $\Pi \leq_{SPR} \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}(I) \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.