On parameterized counting. (English) Zbl 1155.03023

Montoya, Juan Andrés

Freiburg im Breisgau: Univ. Freiburg, Fakultät für Mathematik und Physik (Dissertation). 111 p. (2008).

This PhD thesis has been submitted to the University of Freiburg in 2008, under the supervision of Prof. Jörg Flum, one of the authors of the well-known text in parameterized complexity [J. Flum and M. Grohe, Parametrized complexity theory. Berlin: Springer (2006; Zbl 1143.68016)]. The thesis deals with the complexity of counting problems and their approximations within a parameterized approach.
In complexity theory, a language \(\Sigma\) consisting of words in \(\{0,1\}^*\) raises corresponding search or decision problems: Given \(x\in\{0,1\}^*\), find \(y\in\{0,1\}^*\) such that \((x,y)\in\Sigma\) (in this case, \(x\) is an instance, while \(y\) is a solution), or, given \(z\in\{0,1\}^*\), decide whether \(z\in\Sigma\). The corresponding counting problem consists in determining, for a given instance, how many solutions it possesses. Stockmeyer’s Theorem (1985) asserts that probabilistic approximate counting lies in the second level of the polynomial hierarchy; and Toda’s Theorem (1991) asserts that any problem in the polynomial hierarchy can be reduced to #P-complete problems. A central element in Toda’s proof is Valiant and Vazirani’s Theorem (1986): NP is random reducible to deciding unique solutions for problems in P.
A parameterization is a computable map \(\Sigma\to\mathbb{N}\). For instance, if \(\left(T_n\right)_n\) is a cover of \(\Sigma\), then \(\sigma\mapsto\) (least index \(n\) such that \(\sigma\in T_n\)) is a parameterization. A parameterized problem is thus a language \(\Sigma\) and a parameterization \(\kappa\), or, alternatively, it can be considered as a subset of \(\{0,1\}^*\times\mathbb{N}\).
Given a parameterization \(\kappa\), an algorithm is ftp (fixed-parameter tractable) if for any input \(x\in\{0,1\}^*\) it runs in time \(f(\kappa(x))p(\text{length}(x))\) where \(f\) is a computable map and \(p\) is a polynomial. FTP consists of the languages that can be decided by ftp-algorithms. The notion of ftp-reducibility follows. A parameterized version of SAT asks whether, for any Boolean formula and a parameter \(k\), there is a satisfying assignment with Hamming weight \(k\), and the counting version asks for the number of those satisfying assignments. Then the classes W[P] and #W[P] consist, respectively, of those problems that are ftp-reducible to the parameterized version of SAT and #SAT.
The following operators are introduced on classes of parameterized problems:
(1) \(L\in\exists\cdot{\mathcal C}\Longleftrightarrow\exists \Omega\in{\mathcal C}\), \(f:\mathbb{N}\to\mathbb{N}\) computable:
\[ L= \left\{(x,k)\mid \exists y\in\{0,1\}^{*}: \text{length}(y)\leq f(k)\log(\text{length}(x))\& (x,y,k)\in\Omega\right\}. \]
(2) \(L\in\forall\cdot{\mathcal C}\Longleftrightarrow\exists \Omega\in{\mathcal C}\), \(f:\mathbb{N}\to\mathbb{N}\) computable:
\[ L= \left\{(x,k)\mid \forall y\in\{0,1\}^{*}: \text{length}(y)\leq f(k)\log(\text{length}(x))\;\Rightarrow\;(x,y,k)\in\Omega\right\}. \]
(3) \(L\in\text{BP}\cdot{\mathcal C}\Longleftrightarrow\exists \Omega\in{\mathcal C}\), \(f:\mathbb{N}\to\mathbb{N}\) computable:
\[ (x,k)\in L\Longrightarrow \text{Pr}_{\{y\in\{0,1\}^{*}\mid \text{length}(y)\leq f(k)\log(\text{length}(x))\}}\left[(x,y,k)\in\Omega\right] \geq \tfrac{3}{4} \tag{eq.bp1} \]
\[ (x,k)\not\in L \Longrightarrow \text{Pr}_{\{y\in\{0,1\}^{*}\mid \text{length}(y)\leq f(k)\log(\text{length}(x))\}}\left[(x,y,k)\in\Omega\right] \leq \tfrac{1}{4}\tag{eq.bp2} \]
(4) \(L\in\oplus\cdot{\mathcal C}\Longleftrightarrow\exists \Omega\in{\mathcal C}\), \(f:\mathbb{N}\to\mathbb{N}\) computable: \[ L= \left\{(x,k)\mid\text{card}\{ y\in\{0,1\}^{*}\mid\text{length}(y)\leq f(k)\log(\text{length}(x))\& (x,y,k)\in\Omega\}\equiv 1\bmod 2\right\}. \]
The Weak Probability Amplification states that the bounds \(\frac{3}{4}\) and \(\frac{1}{4}\) in the definition of \(\text{BP}\cdot{\mathcal C}\) can be replaced by \(1-\frac{1}{n}\) and \(\frac{1}{n}\), respectively, by changing the map \(f\) to a particular map \(f_n\).
A parameterized class \({\mathcal C}\) is said to have the probability amplification (pam) property if for any language \(L\in\text{BP}\cdot{\mathcal C}\) the probability bounds in relations ({eq.bp1}) and ({eq.bp2}) can be modified to \(1-2^{-g(k)p(\text{length}(x))}\) and \(2^{-g(k)p(\text{length}(x))}\), respectively. An operator \(\Delta\) on FTP is idempotent if \(\Delta\cdot\Delta\cdot\)FTP\(=\Delta\cdot\)FTP. Then it is seen that BP\(\cdot\oplus\) is idempotent.
Another notion of reducibility is called RP: A parameterized language \(A\) is RP-reducible to another parameterized language \(B\) if there is a probabilistic algorithm \(M\) whose running time is bounded, in time and in space, by \(g(k)p(\text{length}(x))\) for any input \((x,k)\in \{0,1\}^*\times\mathbb{N}\), and whenever \((x,k)\in A\) then with a high probability \(M(x,k)\in B\) whilst if \((x,k)\not\in A\) then with zero probability it may happen that \(M(x,k)\in B\). In the R-reducibility, the last requirement is softened: if \((x,k)\not\in A\) then with a lower probability it may happen that \(M(x,k)\in B\).
The parameterized version of Valiant and Vazirani’s Theorem states that for any language \(L\) in \(\exists\cdot{\mathcal C}\), where \({\mathcal C}\) is a parameterized normal class of languages, \(L\) is RP-reducible to \(\oplus\cdot L\). Or \(\exists\cdot{\mathcal C}\subset \text{BP}\cdot \oplus\cdot L\) whenever the class \({\mathcal C}\) is closed under composition with the majority map \(M_n:\{0,1\}^n\to\{0,1\}\), where \([M_n(x)=1\Longleftrightarrow w_H(x)>\frac{n}{2}]\) and \(w_H\) is the Hamming weight map.
A parameterized analogue of the polynomial hierarchy is introduced in terms of alternating quantifiers. Let PH[P] = \(\bigcup_n \Sigma_n\)FTP. Then the parameterized version of Toda’s Theorem states that if \(\oplus\cdot \text{FTP}\) is closed under composition with the map \(M_n\) then any language in \(\Sigma_n\)FTP is R-reducible to \(\#\)WSAT, and the author poses the questions whether \(\oplus\cdot \text{FTP}\) is closed indeed under composition with the map \(M_n\), and whether the established reductions can be derandomized.
Let \(\#\)W[P] be the parameterized version of the counting problems class \(\#\)P. The approximation of counting problems is determined in the following sense: Given a parameterized counting problem \(\chi\) and \(c\geq 1\), an ftp-algorithm \(M\) approximates \(\chi\) within \(c\) if for all \((x,k)\in\{0,1\}^*\times\mathbb{N}\), \(c^{-1}\leq \frac{M(x,k)}{\chi(x,k)}\leq c\). It is seen that, whenever a \(\#\)W[P]-complete problem (under parsimonious reductions) is approximable by a factor of 2, then it can be approximated by any factor greater than 1. For any counting problem \(\chi\in\#\)W[P] the gap problem p-approx(\(\chi\)) has as Yes-instances the triplets \((x,k,c)\) such that \(\chi(x,k)\geq 2c\), and its No-instances are the triplets \((x,k,c)\) such that \(\chi(x,k)\leq c\). Then it is shown that for any \(\chi\in\#\)W[P] there exists an ftp-algorithm \(M\) that through oracle accesses to p-approx(\(\chi\)) approximates \(\chi\) by a factor of 2 making a number of queries bounded by \(g(k)\log(\text{length}(x))\), where \(g\) is a computable map. It is shown, using hashing arguments, that the gap problems p-approx(\(\chi\)) fall in the class BP\(\cdot\exists\cdot\)FTP. It is also shown that \(\text{BP}\cdot\text{FTP}\subset (\exists\cdot\forall\cdot\text{FTP})\cap (\forall\cdot\exists\cdot\text{FTP})\) and that \(\text{BP}\cdot \exists\cdot\text{FTP}\subset (\forall\cdot\exists\cdot\text{FTP})\) provided that W[P] is closed by conjunctions.
From this there follows the parameterized version of Stockmeyer’s Theorem: If W[P] is closed under conjunctions then approximate counting belongs to the second level of the parameterized polynomial hierarchy, or, in a relaxed way, if W[P] has the pam property then approximate counting belongs to the third level of the parameterized polynomial hierarchy. The author poses as an open question to decide whether W[P] is closed under conjunctions. Then he deals with the plausibility of the hypothesis that the pam property does hold in W[P]. Since the second level of the polynomial hierarchy BP\(\cdot\exists\cdot\)P corresponds to the Arthur-Merlin interactive proof games, the author analyzes the parameterized Arthur-Merlin class and probability amplification and he manages to prove that W[P] is closed under conjunctions if and only if a restricted parameterized version of SAT lies within W[P]. It is also proven that if W[P] is not closed under conjunctions then the pam property may also fail to hold.
Finally, the thesis presents some basic facts of the parameterized polynomial hierarchy, in terms of machine and descriptive set theory characterizations of the classes in the hierarchy.

Reviewer: Guillermo Morales-Luna (Mexico)

MSC:

03D15	Complexity of computation (including implicit computational complexity)
03-02	Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25	Analysis of algorithms and problem complexity

Keywords:

parameterized complexity; approximation of counting problems

Citations:

Zbl 1143.68016