Descriptive Complexity of Parameterised Counting Classes

Parameterised complexity theory (Downey, Fellows 1999) is about considering parameterisations of problems to better determine the difficulty of problems. A simple example of such parameterisations can be made for the satisfiability problem of propositional logic (SAT). Here, the parameter number of variables is rather unsatisfactory. Clearly, one can solve SAT in time 2•|Vars(F)|•|F|, where F is the considered formula, but usually the number of variables is not assumed to be constant. Yet, problems that can be solved in such a runtime as above are called fixed-parameter tractable (or short, in FPT). Often the parameter is assumed to be slowly growing or even constant. In such a case, the aforementioned runtime is polynomial and the degree of the polynomial is independent of the value of the parameter. In contrast to that we have runtimes of the form n•f(k) which corresponding problems are summarised by the class XP. Between FPT and XP a hierarchy of so-called weft-classes W[i] exist: FPT ⊆ W[1] ⊆⋯⊆ XP. However, it is unknown whether any of the inclusions are strict.

Counting problems play a pivotal role in many breakthroughs in structural complexity theory. One decade ago, Flum and Grohe (2002) developed a theory of parameterised counting problems. Flum and Grohe showed that counting cycles of length k in a directed graph is complete for the class #W[1] (which is the counting version of W[1]; usually the number of accepting paths are counted). Furthermore, they used counting of solutions of model checking problems of first-order logic to characterise the #A-hierarchy. Despite intensive research efforts, translating classical results, e.g., the theorem of Toda, to the parameterised setting has been unsuccessful yet.

In the area of descriptive complexity theory one characterises complexity classes with sets of formulas. In a breakthrough result of Fagin (1973), he showed that the class NP coincides with the set of all existential second-order formulas. From Immerman (1982) we know a characterisation of the class P as well as regular languages being characterised by MSO formulas. Saluja and Subrahmaniam (1998) reached a logical characterisation of #P through counting models of FO formulas. Moreover, Kontinen (2008) classified the counting hierarchy by logics with generalised quantifiers. Flum and Grohe showed 2003 that logical characterisations of classical classes as P, NP and PSPACE can be transferred to the parameterised approach. Furthermore, they proved a logical characterisation of the W*-hierarchy in 2007.

In this area, we want to characterise parameterised decision- and counting-classes by sets of formulas. We decide the work into two parts.

1. Characterisations of parameterised complexity classes
   As already explained, the W*-hierarchy embodies a Fagin-like characterisation. However, up to today no such approach for the W-hierarchy, FPT or other classes with restrictions on parallelism and space exists. We plan logical characterisations of FPT and parameterised variants of complexity classes as, e.g., para-AC[0], para-WNC[1], para-WL and para-WNL which have been introduced by Elberfeld, Stockhusen and Tantau (2015).
2. Characterisations of parameterised counting classes
   Until today no logical characterisations of the parameterised counting classes of Flum and Grohe are known. We want to describe classes in the the #W-hierarchy. More precisely, we want to work at the following challenges:
   1. Find characterisations of #W[1] and #W[P] with respect to counting over FO and other related logics.
   2. Find logical characterisations of parameterised analogues of the polynomial-time hierarchy of Montoya (2008).
   3. Translate logical characterisations of the counting hierarchy of Kontinen (2009) to the parameterised setting.

Within both parts, we will study parameterisations of natural counting problems as, e.g., counting paths in directed graphs or paths in push-down automatons. Furthermore, the question how tools of finite model theory (locality, Ehrenfeucht-Fraïssé games, Zero-One Laws, ...) can be utilised to find answers to the questions of above.