The theory of parameterised complexity (Downey, Fellows 1999) considers so-called parameterisations in order to better understand the inherent difficulty of problems. A simple example of such a parameterisation for the satisfiability problem of propositional formulas (SAT) is the number of variables of a given formula. Under this parameterisation, SAT can be solved in a runtime of 2•|Vars(F)|•|F|, where F is the given formula. Such runtimes are said to be ‘fixed-parameter tractable’ (or, in short, FPT). This means that, when the parameter is considered constant, the runtime is polynomial and the degree of the polynomial does not depend on the value of the parameter. In contrast to this are running times of the form n•f(k), where the corresponding problems are summarised in the class XP (for input length n). A hierarchy of so-called ‘Weft’ classes W[i] exists between FPT and XP. It is not known whether any of the inclusions from W[i] to W[i+1] is strict or whether FPT is strictly contained in W[1].

Counting problems have played a key role in many breakthroughs in structural complexity theory. A decade ago, Flum and Grohe (2002) developed a theory of parameterised counting problems. Flum and Grohe showed that counting cycles of length k in an oriented graph is #P=W[1]-complete (which is the counting version of class W[1]; usually, the number of accepting paths is counted here). Furthermore, cycle counting of solutions of model-checking problems for first-order logic was used to characterise the so-called #A hierarchy. Despite intensive research efforts, so far there has been no success in translating classical results, such as the Toda theorem, into the parameterised world.

In descriptive complexity theory, complexity classes are characterised by sets of formulas. In a groundbreaking result, Fagin (1973) showed that the class NP coincides with the set of all existential second-order formulas. Immerman (1982) provided a characterisation of the class P and showed that regular languages can be characterised by monadic second-order formulas (MSO). Saluja and Subrahmaniam (1998) achieved a logical characterisation of #P by counting models of an FO formula. Furthermore, Kontinen (2008) classified the counting hierarchy by logics with generalized quantifiers. In 2003, Flum and Grohe showed that logical characterizations of classical complexity classes, such as P, NP and PSPACE, can also be transferred to the parameterized approach. Furthermore, in 2007 they gave a logical characterization of the W* hierarchy.

In this project, we want to characterise parameterised decision and counting classes in terms of sets of logical formulas. We divide the project into two sections.

Characterisation of parameterised complexity classes
As already mentioned, the W* hierarchy has a Fagin-type characterisation by logical formulas. However, there is no such approach for the W hierarchy, for FPT or for other classes that are restricted with respect to parallelism and space. We plan to find logical characterisations of FPT and parameterised variants of complexity classes, such as para-AC[0], para-WNC[1], para-WL and para-WNL, which were defined by Elberfeld, Stockhusen and Tantau (2015).
Characterisation of parameterised counting classes
So far, no logical characterisations of the parameterised counting classes introduced by Flum and Grohe are known. We aim to describe classes within the #W[P] hierarchy. More precisely, we will work on the following questions:
Find characterisations of #W[1] and #W[P] with respect to counting in FO or other associated logics.
Find logical characterisations of the parameterised analogues of Montoya's polynomial time hierarchy (2008).
Attempt to transfer the logical characterisation of Kontinen's counting hierarchy (2009) to the parameterised setting.
Within both sections, we will study parameterisations of natural counting problems, such as counting paths in directed graphs or paths in pushdown automata. Furthermore, the question arises as to how tools from finite model theory (locality, Ehrenfeucht-Fraïssé games, zero-one laws,...) can be used to find answers to the above questions.