https://reductions.network/parsimonious

1<!DOCTYPE html>
2<html lang="en">
3    <head>
4        

4<script src="scripts/html/generateStaticPage.js" type="module"></script>

4
5        <link rel="stylesheet" href="styles/noscript.css">
6        <!-- preload style need to be included here so that they dont need to be loaded-->
7        <style>
8            .preload {
9                visibility: hidden;
10            }
11        </style>
12    </head>
13    <body>
14        <noscript><div class="noscript">You need to enable Java-Script to run this page.</div></noscript>
15        

15<script src="scripts/elements/header.js"></script>

15
16
17        <h1>Parsimonious Reductions</h1>
18
19        <article>
20
21            <p>
22                A parsimonious reduction is a transformation from one problem to another problem such that
23                the number of solutions is preserved.
24                More precisely, a parsimonious reduction is a typical (polynomial time) many-one reduction that additionally
25                does not increase the number of solutions in the transformed instance.
26
27                Parsimonious reductions are used to prove hardness for counting complexity classes, such as $\#P$.
28            </p>
29
30            <h3>Definitions</h3>
31
32            <p>
33                For a formal definition of parsimonious reductions, we first define a computational problem as a tuple of a language
34                with a corresponding solution set, which include the certificates encoded as strings of 0s and 1s.
35            </p>
36
37            <p>
38                <b>Definition (Computational problem)</b>
39                A computational problem $\Pi$ is a tuple $(\mathcal{I},\mathcal{S})$, such that
40            <ul>
41                <li>$\mathcal{I} \subseteq \{0,1\}^*$ is a language. We call $\mathcal{I}$ the set of instances of $\Pi$.</li>
42                <li>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$.</li>
43            </ul>
44            </p>
45
46            <p>
47                There are several notions on parsimonious reductions.
48                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.
49                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.
50                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.
51                Accordingly, strongly parsimonious reductions are also weakly parsimonious.
52            </p>
53
54            <p>
55                <b>Definition (Strongly Parsimonious Reduction)</b>
56                Let $\Pi = (\mathcal{I},\mathcal{S})$ and $\Pi' = (\mathcal{I}',\mathcal{S}')$ be two computational problems.
57                We say that there is a strongly parsimonious reduction from $\Pi$ to $\Pi'$, and write $\Pi \leq_{SPR} \Pi'$, if
58            <ul>
59                <li>
60                    There exists a function $g: \{0,1\}^* \rightarrow \{0,1\}^*$ computable in polynomial time in the input size $|I|$,
61                    such that $I$ is a Yes-instance iff $g(I)$ is a Yes-instance
62                    (i.e. $\mathcal{S}(I) \neq \emptyset$ iff $\mathcal{S}'(g(I)) = \emptyset$).
63                </li>
64                <li>
65                    There exist functions $(p_I)_{I \in \mathcal{I}}$ computable in polynomial time in $|I|$ such that for all instances $I \in \mathcal{I}$,
66                    $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)$.
67                </li>
68            </ul>
69            </p>
70
71
72            <h3>Applications</h3>
73            <p>
74                Parsimonious reductions are used to show hardness for counting complexity classes.
75                Among these are
76            <ul>
77                <li>
78                    $\#P$, the class of problems, for which to count the number of accepting paths of a non-deterministic polynomial time Turing machine.
79                    The canonical complete problems are $\#$SAT, i.e. counting the number satisfying assignments of a Boolean formula, and
80                    01-PERMANENT, i.e. computing the permanent of a 01-matrix.
81                </li>
82                <li>
83                    $\#W[t]$, which is the analogue of $\#P$ in the parameterized world.
84                    Here not polynomial many-one parsimonious reductions are used, but parsimonious FPT-reductions.
85                    The canonical complete problem is $\#$Weighted-Weft-$t$-Circuit-SAT.
86                </li>
87            </ul>
88            </p>
89        </article>
90    </body>
91</html>
92
93
94
95
96
97