Incremental FPT Delay

Abstract

In this paper, we study the relationship of parameterized enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce two hierarchies (IncFPTa and CapIncFPTa) of enumeration complexity classes for incremental fpt-time in terms of exponent slices and show how they interleave. Furthermore, we define several parameterized function classes and, in particular, introduce the parameterized counterpart of the class of nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist, TFNP, known from Megiddo and Papadimitriou (TCS 1991). We show that this class TF(para-NP), the restriction of the function variant of NP to total functions, collapsing to F(FPT), the function variant of FPT, is equivalent to the result that OutputFPT coincides with IncFPT. In addition, these collapses are shown to be equivalent to TFNP = FP, and also equivalent to P equals NP intersected with coNP. Finally, we show that these two collapses are equivalent to the collapse of IncP and OutputP in the classical setting. These results are the first direct connections of collapses in parameterized enumeration complexity to collapses in classical enumeration complexity, parameterized function complexity, classical function complexity, and computational complexity theory.

1. Introduction

1.1. Enumeration

In 1988, Johnson, Papadimitriou, and Yannakakis [1] laid the cornerstone of enumeration algorithms. In modern times of ubiquitous computing, such algorithms are of central importance in several areas of life and research such as combinatorics, computational geometry, and operations research [2]. Beyond that, recent results unveil major importance in web search, data mining, bioinformatics, and computational linguistics [3]. Moreover, there are connections to formal languages on enumeration problems for probabilistic automata [4].

Clearly, for enumeration algorithms, one is not primarily interested in their runtime complexity, whereas the time elapsed between two consecutive outputs of such an algorithm is of utmost interest. As a result, one measures the delay of such algorithms. The main goal is to achieve a uniform stream of printed solutions. In this context, the complexity class $\mathsf{DelayP}$, that is, polynomial delay, is regarded as an efficient way of enumeration. Enumeration algorithms for problems in that particular class print every $p(|x|)$-many-steps a new and distinct solution (where x is the input and p is a fixed polynomial). Interestingly, there is exists a class of incremental polynomial delay, $\mathsf{IncP}$, which contains problems that allow for enumeration algorithms whose delay increases in the process of computation. Intuitively, this captures the idea that after printing ‘obvious’ solutions, later in the process, it becomes difficult to find new outputs. More precisely, the delay between output i and $i+1$ is bounded by a polynomial in the input length and in i. Consequently, in the beginning, such an algorithm possesses a polynomial delay, whereas later, it eventually becomes exponential (for problems with exponentially many solutions, which is rather a common phenomenon). While prominent problems in the class $\mathsf{DelayP}$ are the enumeration of satisfying assignments for Horn or Krom formulas [5], the enumeration of structures for first-order query problems with possibly free second-order variables and at most one existential quantifier [6], or the enumeration of cycles in graphs [7], rather a limited amount of research has been invested in understanding $\mathsf{IncP}$. A well-studied problem in this enumeration complexity class is the task of generating all maximal solutions of systems of equations modulo 2 [8]. Even today, it is not clear whether this problem can be solved with a polynomial delay. Another example of problems in $\mathsf{IncP}$ is the task to enumerate conjuncts in the context of monotone dualization of DNF formulas investigated by Eiter et al. [9], and Fredman and Khachiyan [10]. The significance of these results stems from the connection to computing minimal hypergraph transversals. A more recent result, which is not known to be in $\mathsf{DelayP}$ and not equivalent to the enumeration of transversals in hypergraphs of fixed edge size, was shown to be a member of $\mathsf{IncP}$ by Carmeli et al. [11]: the task to enumerate all minimal triangulations of a given graph. In 2017, Capelli and Strozecki [12] investigated $\mathsf{IncP}$ and its relationship to other classical enumeration classes in depth, greatly improving the overall understanding of incremental polynomial delay. One of their central results for this paper shows that if the function variant of $\mathsf{NP}$ restricted to total functions coincides with $\mathsf{F}\mathsf{P}$, then we have a collapse of incremental polynomial time with $\mathsf{OutputP}$, the class of problems for which all solutions can be enumerated in time polynomial in the input length and in the solution set size (see Proposition 4 on page 4). Furthermore, Capelli and Strozecki studied exponent sliced versions of incremental time and showed that this hierarchy of classes strictly interleaves ([12], Proposition 16).

1.2. Parameterized Complexity

The framework of parameterized complexity [13,14,15,16] allows one to approach a fine-grained complexity analysis of problems beyond classical worst-case complexity. Here, one considers a problem together with a parameter and tries to achieve deterministic runtimes of the form $f(\kappa (x))·p(|x|)$, where $\kappa (x)$ is the value of the parameter of an instance x (note that the parameter does not depend on the input length), p is a polynomial, and f is an arbitrary computable function. Problems that can be solved by algorithms within these runtime bounds belong to the class $\mathsf{FPT}$. The class name abbreviates ‘fixed-parameter tractable’ and is justified by the observation that a relevant parameter is seen be slowly growing or even of constant value [17].

A rather large parameterized complexity class is $\mathsf{para}$-$\mathsf{NP}$, the nondeterministic counterpart of $\mathsf{FPT}$, which is defined via nondeterministic runtimes of the same form of $f(\kappa (x))·p(|x|)$. By definition of the classes, the inclusion $\mathsf{FPT}\subseteq \mathsf{para}$-$\mathsf{NP}$ is immediate. Nonetheless, compared to the situation on the classical complexity side, $\mathsf{para}$-$\mathsf{NP}$ is not seen as a counterpart of $\mathsf{NP}$ in the sense of intractability. In fact, $\mathsf{W}\left[1\right]$ is the class which usually is used to show intractability lower bounds in the parameterized setting. This class is part of an infinite $\mathsf{W}$-hierarchy in between the aforementioned two classes. It is not known whether any of the inclusions of the intermediate classes is strict or not.

1.3. Parameterized Enumeration

Recently, Creignou et al. [18,19,20,21] developed a framework of parameterized enumeration allowing for fine-grained complexity analyses of enumeration problems. In analogue to classical enumeration complexity, there are the classes $\mathsf{DelayFPT}$ and $\mathsf{IncFPT}$, and it is unknown if $\mathsf{DelayFPT}⊊\mathsf{IncFPT}$ is true or not. Here, for problems in $\mathsf{IncFPT}$, enumeration algorithms exist which print solutions with a delay of the form $t(\kappa (x))·p(|x|,i)$, where t is a computable function, $\kappa$ the parameterization, x the input, and i is the index of the currently printed solution. Similarly, problems in $\mathsf{DelayFPT}$ allow for enumeration algorithms running with an fpt-delay.

In their research, Creignou et al. [20] noticed that for some problems, enumerating solutions by increasing size is possible with $\mathsf{DelayFPT}$ and exponential space (such as triangulations of graphs, or cluster editings). However, it is not clear how to circumvent the unsatisfactory space requirement. Recently, Meier and Reinbold [22] observed a similar phenomenon. They studied the enumeration complexity of problems in a modern family of logics of dependence and independence. In the context of dependence statements, single assignments do not make sense. As a result, one introduces team semantics defining semantics with respect to sets of assignments, which are commonly called teams. Meier and Reinbold showed that in the process of enumerating satisfying teams for formulas of a specific Dependence Logic fragment, it seemed that an $\mathsf{FPT}$ delay required exponential space in this particular setting. While reaching polynomial space for the same problem, the price was paid by an increasing delay, $\mathsf{IncFPT}$, and it was not clear how to avoid the increase of the delay while maintaining a polynomial space threshold. This is a significant question of research, and we improve the understanding of this question by pointing out connections to classical enumeration complexity where similar phenomena have been observed [12] (see also the discussion in the beginning of Section 4).

1.4. Related Work

In 1991, Megiddo and Papadimitriou [23] introduced the function complexity class $\mathsf{TF}\mathsf{NP}$ and studied problems within this class. In a recent investigation, Goldberg and Papadimitriou introduced a rich theory around this complexity class that also features several aspects of proof theory [24]. Additionally, the investigations of Capelli and Strozecki [12] on probabilistic classes might yield further connections to the enumeration setting via the parameterized analogues of probabilistic computation of Chauhan and Rao [25]. Furthermore, Fichte et al. [26] studied the parameterized complexity of default logic and present in their work a parameterized enumeration algorithm outputting stable extensions. It might be worth further analyzing problems in this setting, possibly yielding $\mathsf{IncFPT}$ algorithms. Quite recently, Bläsius et al. [27] considered the enumeration of minimal hitting sets in lexicographical order and devised some cases which allow for $\mathsf{DelayP}$-, resp., $\mathsf{DelayFPT}$-algorithms. Furthermore, Pichler et al. [28] showed enumeration complexity results for problems on MSO (monadic second order logic) formulas. Finally, investigations of Mary and Strozecki [29] are related to the $\mathsf{IncP}$-versus-$\mathsf{DelayP}$ question from the perspective of closure operations. Counting classes in the parameterized setting have been introduced by Flum and Grohe [30] as well as by McCartin [31]. Very recently, Roth and Wellnitz [32] presented a thorough study of counting and finding homomorphisms and showed how their results improve the understanding of the class #$\mathsf{W}\left[1\right]$ (the counting variant of $\mathsf{W}\left[1\right]$). The understanding of this class has been improved also by a line of previous research, e.g., the works of Curticapean, Dell, and Roth [33] as well as of Roth and Schmitt [34] (and more recently, together with Dörfler and Wellnitz [35]). The thesis of Curticapean [36] also presents a nice overview of this field.

1.5. Our Contribution

We improve the understanding of incremental enumeration time by connecting classical enumeration complexity to the very young field of parameterized enumeration complexity. Although we cannot answer the aforementioned time–space tradeoff question in either a positive or negative way, we hope that the presented “bridge” to parameterized enumeration will be helpful for future research. Capelli and Strozecki [12] distinguished two kinds of incremental polynomial time enumeration, which we call $\mathsf{IncP}$ and $\mathsf{CapIncP}$. Essentially, the difference of these two classes lies in the perspective of the delay. For $\mathsf{IncP}$, one measures the delay between an output solution i and $i+1$, which has to be polynomial in i and the input length. For $\mathsf{CapIncP}$, the output of i solutions has to be polynomial in i and the input length. This means that for the latter class, the output stream must not be as uniform as for the former. In Section 4, we introduce several parameterized function classes (a good overview of the classes can be found in Table 1 on page 11) that are utilized to prove our main result: $\mathsf{IncFPT}=\mathsf{OutputFPT}$ if and only if $\mathsf{IncP}=\mathsf{OutputP}$ (Corollary 4). This is the first result that directly connects the classical with the parameterized enumeration setting. Through this approach, separating the classical classes then implies separating the parameterized counterparts and vice versa. Moreover, we introduce two hierarchies of parameterized incremental time ${\mathsf{IncFPT}}_a$ and ${\mathsf{CapIncFPT}}_a$ (where $a\in \mathbb{N}$ is a class parameter that restricts the exponent of the polynomial for the solution index) in Section 3, show how they interleave and thereby provide some new insights into the interplay of $\mathsf{FPT}$ delay and incremental $\mathsf{FPT}$ delay. One of the previously mentioned parameterized function classes, $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$, is a counterpart of the class $\mathsf{TF}\mathsf{NP}$, the class of nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist, known from Megiddo and Papadimitriou [23]. For this class, the algorithmic task is to guess a witness y such that $(x,y)\in A$, where A is a total relation. It is important to note that this class summarizes significant cryptography-related problems such as factoring or the discrete logarithm modulo a (certified) prime p of a (certified) primitive root x of p (see the textbook of Talbot and Welsh [37] on cryptography-related problems). Clearly, parameterized versions of these problems are members in $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$ via trivial parameterization ${\kappa }_{\mathrm{one}}(x)=1$.

Boiling down the presented results yields a list of equivalent collapse results and thereby connects a wealth of different fields of research: parameterized enumeration, classical enumeration, parameterized function complexity, classical function complexity, and computational complexity theory. Our second central result is summarized in Corollary 3 on page 15.

1.6. Outline

In Section 2, we introduce the necessary notions of parameterized complexity theory and (parameterized) enumeration algorithms. Then, we continue in Section 3 to present two hierarchies of parameterized incremental $\mathsf{FPT}$ enumeration classes and study the relation to $\mathsf{DelayFPT}$. Eventually, in Section 4, we introduce several parameterized function classes and outline connections to the parameterized enumeration classes. There, we connect a collapse of the two function classes $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$ and $\mathsf{F}(\mathsf{FPT})$ to a collapse of $\mathsf{OutputFPT}$ and $\mathsf{CapIncFPT}$, extend this collapse to $\mathsf{TF}\mathsf{NP}$ and $\mathsf{F}\mathsf{P}$ (thus, in the classical function complexity setting), and further reach out for our main result showing $\mathsf{OutputFPT}=\mathsf{IncFPT}$ if and only if $\mathsf{OutputP}=\mathsf{IncP}$. Finally, we conclude and present questions for future research.

2. Preliminaries

Enumeration algorithms are usually running in exponential time as the solution space is of this particular size. As Turing machines cannot access specific bits of exponentially sized data in polynomial time, one commonly uses the RAM model as the machinery of choice; see, for instance, the work of Johnson et al. [1] or, more recently, of Creignou et al. [38]. For our purposes, polynomially restricted RAMs (RAMs where each register content is polynomially bounded with respect to the input size) suffice. We make use of the standard complexity classes $\mathsf{P}$ and $\mathsf{NP}$. An introduction into this field can be found in the textbook of Pippenger [39].

2.1. Parameterized Complexity Theory

We present a brief introduction into the field of parameterized complexity theory. For a deeper introduction, we kindly refer the reader to the textbooks of Flum and Grohe [15], Niedermeyer [16], or Downey and Fellows [13].

Let $Q\subseteq {\Sigma }^{*}$ be a decision problem over some alphabet $\Sigma$. Given an instance $\langle x,k\rangle \in Q\times \mathbb{N}$, we call k the parameter’s value (of x). Often, instead of using tuple notation for instances, one uses a polynomial time computable function $\kappa :{\Sigma }^{*}\to \mathbb{N}$ (the parameterization) to address the parameter’s value of an input x. Then, we write $(Q,\kappa )$ denoting the parameterized problem (PP).

Definition 1

(Fixed-parameter tractable). Let $(Q,\kappa )$ be a parameterized problem over some alphabet Σ. If there exists a deterministic algorithm A and a computable function $f:\mathbb{N}\to \mathbb{N}$ such that for all $x\in {\Sigma }^{*}$

• A accepts x if and only if $x\in Q$, and
• A has a runtime of $f(\kappa (x))·{|x|}^{O(1)}$,

Then A is an fpt-algorithm for $(Q,\kappa )$ and $(Q,\kappa )$ is fixed-parameter tractable (or short, in the complexity class $\mathsf{FPT}$).

Flum and Grohe [15] provide a way to “parameterize” a classical and robust complexity class. For our purposes, $\mathsf{para}$-$\mathsf{NP}$ suffices, and accordingly, we do not present the general scheme.

Definition 2

($\mathsf{para}$-$\mathsf{NP}$, ([15], Definition 2.10)). Let $(Q,\kappa )$ with $Q\subseteq {\Sigma }^{*}$ be a parameterized problem over some alphabet Σ. We have $(Q,\kappa )\in \mathsf{para}$-$\mathsf{NP}$ if there exists a computable function $f:\mathbb{N}\to \mathbb{N}$ and a nondeterministic algorithm N such that for all $x\in {\Sigma }^{*}$, N correctly decides whether $x\in Q$ in at most $f(\kappa (x))·p(|x|)$ steps, where p is a polynomial.

Furthermore, Flum and Grohe characterize the class $\mathsf{para}$-$\mathsf{NP}$ via all problems “that are in $\mathsf{NP}$ after precomputation on the parameter”.

Proposition 1

([15], Proposition 2.12). Let $(Q,\kappa )$ be a parameterized problem over some alphabet Σ. We have $(Q,\kappa )\in \mathsf{para}$-$\mathsf{NP}$ if and only if there exists a computable function $\pi :{\Sigma }^{*}\to {\Sigma }^{*}$ and a problem $Q^{\prime }\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ such that $Q^{\prime }\in \mathsf{NP}$ and the following is true: For all instances $x\in {\Sigma }^{*}$, we have that $x\in Q$ if and only if $(x,\pi (\kappa (x)))\in Q^{\prime }$.

According to the well-known characterization of the complexity class $\mathsf{NP}$ via a verifier language, one can easily deduce the following corollary, which is later utilized to explain Definition 11.

Corollary 1.

Let $(Q,\kappa )$ be a parameterized problem over some alphabet Σ and p some polynomial. We have $(Q,\kappa )\in \mathsf{para}$-$\mathsf{NP}$ if there exists a computable function $\pi :{\Sigma }^{*}\to {\Sigma }^{*}$ and a problem $Q^{\prime }\subseteq {\Sigma }^{*}\times {\Sigma }^{*}\times {\Sigma }^{*}$ such that $Q^{\prime }\in \mathsf{P}$ and the following is true: For all instances $x\in {\Sigma }^{*}$, we have that $x\in Q$ if and only if there exists a y such that $|y|\le p(|x|)$ and $(x,\pi (\kappa (x)),y)\in Q^{\prime }$.

2.2. Enumeration

As already motivated in the beginning of this section, measuring the runtime of enumeration algorithms is usually abandoned beyond the study of $\mathsf{OutputP}$. As a result, one inspects the uniformity of the flow of output solutions of these algorithms rather than their total running time. In view of this, one measures the delay between two consecutive outputs. Johnson et al. [1] laid the cornerstone of this intuition in a seminal paper and introduced the necessary tools and complexity notions. Creignou, Olive, and Schmidt [3,40] presented recent notions in this framework, which we aim to follow. In this paper, we only consider enumeration problems which are “good” in the sense of polynomially bounded solution lengths and polynomially verifiable solutions (Capelli and Strozecki [12] call the corresponding class EnumP). A good textbook that introduces into the field of exact exponential algorithms is by Fomin and Kratsch [41].

Definition 3

(NP Enumeration Problem). An NP enumeration problem (EP) over an alphabet Σ is a tuple $E=(Q,\mathrm{Sol})$, where

• $Q\subseteq {\Sigma }^{*}$ is the set of instances (recognizable in polynomial time),
• $\mathrm{Sol}:{\Sigma }^{*}\to \mathcal{P}({\Sigma }^{*})$ is a computable function such that for all $x\in {\Sigma }^{*}$, $\mathrm{Sol}(x)$ is a finite set and $\mathrm{Sol}(x)\ne \varnothing$ if and only if $x\in Q$,
• $\left\{(x,y)\mid y\in \mathrm{Sol}(x)\right\}\in \mathsf{P}$, and
• there exists a polynomial p such that for all $x\in Q$ and $y\in \mathrm{Sol}(x)$ we have $|y|\le p(|x|)$.

Furthermore, we use the shorthand $\mathcal{S}={\bigcup }_{x\in Q}\mathrm{Sol}(x)$ to refer to the set of solutions for every possible instance. If $E=(Q,\mathrm{Sol})$ is an EP over the alphabet $\Sigma$, then we call strings $x\in {\Sigma }^{*}$ instances of E, and $\mathrm{Sol}(x)$ the set of solutions of x.

An enumeration algorithm (EA) $\mathcal{A}$ for the EP $E=(Q,\mathrm{Sol})$ is a deterministic algorithm which, on the input x of E, outputs exactly the elements of $\mathrm{Sol}(x)$ without duplicates, and which terminates after a finite number of steps on every input. The following definition fixes the ideas of measuring the ‘flow of output solutions’.

Definition 4

(Delay). Let $E=(Q,\mathrm{Sol})$ be an enumeration problem and $\mathcal{A}$ be an enumeration algorithm for E. For $x\in Q$, we define the i-th delay of $\mathcal{A}$ as the time between outputting the i-th and $(i+1)$-st solution in $\mathrm{Sol}(x)$. Furthermore, we set the 0-th delay to be the precomputation phase, which is the time from the start of the computation to the first output statement. Analogously, the n-th delay, for $n=|\mathrm{Sol}(x)|$, is the postcomputation phase, which is the time needed after the last output statement until $\mathcal{A}$ terminates. If $t:\mathbb{N}\to \mathbb{N}$, then, generally, $\mathcal{A}$ is said to output $\mathrm{Sol}(x)$ with delay$O(t(|x|))$ if for all $x\in Q$ and all $i\in \mathbb{N}$ the i-th delay is in $O(t(|x|))$.

Subsequently, we use the notion of delay to state the central enumeration complexity classes.

Definition 5.

Let $E=(Q,\mathrm{Sol})$ be an enumeration problem and $\mathcal{A}$ be an enumeration algorithm for E. Then, $\mathcal{A}$ is

• a $\mathsf{P}$-$\mathsf{enum}$-algorithm if and only if there exists a polynomial p such that for all $x\in Q$, algorithm $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ in time $O(p(|x|))$.
• a $\mathsf{DelayP}$-algorithm if and only if there exists a polynomial p such that for all $x\in Q$, algorithm $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ with delay $O(p(|x|))$.
• an $\mathsf{IncP}$-algorithm if and only if there exists a polynomial p such that for all $x\in Q$, algorithm $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ and its i-th delay is in $O(p(|x|,i))$ (for every $0\le i\le |\mathrm{Sol}(x)|$).
• a ${\mathsf{CapIncP}}_a$-algorithm if and only if there exists a polynomial p such that for all $x\in Q$, algorithm $\mathcal{A}$ outputs i elements of $\mathrm{Sol}(x)$ in time $O(p(|x|)·i^a)$ (for every $0\le i\le |\mathrm{Sol}(x)|$).
• a $\mathsf{OutputP}$-algorithm if and only if there exists a polynomial p such that for all $x\in Q$, algorithm $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ in time $O(p(|x|,|\mathrm{Sol}(x)|))$.

Then, we say E is in $\mathsf{P}$-$\mathsf{enum}$/$\mathsf{DelayP}$/$\mathsf{IncP}$/${\mathsf{CapIncP}}_a$/$\mathsf{OutputP}$ if E admits an $\mathsf{P}$-$\mathsf{enum}$-/$\mathsf{DelayP}$-/$\mathsf{IncP}$-/${\mathsf{CapIncP}}_a$-/$\mathsf{OutputP}$-algorithm. Finally, we define $\mathsf{CapIncP}:={\bigcup }_{a\in \mathbb{N}}{\mathsf{CapIncP}}_a$.

Note that in the diploma thesis of Schmidt ([40], Section 3.1), the class $\mathsf{P}$-$\mathsf{enum}$ is called $\mathsf{TotalP}$. We avoid this name to prevent possible confusion with class names defined in the following section as well as with the work of Capelli and Strozecki [12]. Additionally, we want to point out that Capelli and Strozecki use the definition of $\mathsf{CapIncP}$ for $\mathsf{IncP}$ (and use the name “$\mathsf{UsualIncP}$” for $\mathsf{IncP}$ instead). They prove that the notions of $\mathsf{CapIncP}$ and $\mathsf{IncP}$ are equivalent up to an exponential space requirement when using a structured delay. The idea for the following proposition is that we can wait to output previously computed solutions.

Proposition 2

([12], Corollary 13). Without any space restrictions we have that $\mathsf{CapIncP}=\mathsf{IncP}$.

After studying the definition of the class $\mathsf{CapIncP}$, one could easily come to the opinion that the class is more general than $\mathsf{IncP}$ because it does not necessarily have a uniform delay. However, the previous proposition told us that this is not true.

2.3. Parameterized Enumeration

Having introduced the basic principles in parameterized complexity theory and enumeration complexity theory, we introduce a combined version of these notions.

Definition 6

([19]). A parameterized enumeration problem (PEP) over an alphabet Σ is a triple $E=(Q,\kappa ,\mathrm{Sol})$, where

• $\kappa :{\Sigma }^{*}\to \mathbb{N}$ is a parameterization (that is, a polynomial-time computable function), and
• $(Q,\mathrm{Sol})$ is an EP.

The definitions of enumeration algorithms and delays are easily lifted to the setting of PEPs. Observe that the following defined classes are in complete analogy to the nonparameterized case from the previous section.

Definition 7

([19]). Let $E=(Q,\kappa ,\mathrm{Sol})$ be a PEP and $\mathcal{A}$ an enumeration algorithm for E. Then the algorithm $\mathcal{A}$ is

• an $\mathsf{FPT}$-enumeration algorithm if there exists a computable function $t:\mathbb{N}\to \mathbb{N}$ and a polynomial p such that for every instance $x\in {\Sigma }^{*}$, $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ in time at most $t(\kappa (x))·p(|x|)$,
• a $\mathsf{DelayFPT}$-algorithm if there exists a computable function $t:\mathbb{N}\to \mathbb{N}$ and a polynomial p such that for every $x\in {\Sigma }^{*}$, $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ with delay of at most $t(\kappa (x))·p(|x|)$,
• an $\mathsf{IncFPT}$-algorithm if there exists a computable function $t:\mathbb{N}\to \mathbb{N}$ and a polynomial p such that for every $x\in {\Sigma }^{*}$, $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ and its i-th delay is at most $t(\kappa (x))·p(|x|,i)$, and
• an $\mathsf{OutputFPT}$-algorithm if there exists a computable function $t:\mathbb{N}\to \mathbb{N}$ and a polynomial p such that for every instance $x\in {\Sigma }^{*}$, $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ in time at most $t(\kappa (x))·p(|x|,|\mathrm{Sol}(x)|)$.

Note that, as before, the notion of $\mathsf{TotalFPT}$ has been used for the class of $\mathsf{FPT}$-enumerable problems [18]. We avoid this name as it causes confusion with respect to an enumeration class $\mathsf{TotalP}$ ([40], Section 3.1), which takes into account not only the size of the input but also the number of solutions. We call this class $\mathsf{OutputP}$ instead and, accordingly, it is the nonparameterized analogue of the above class $\mathsf{OutputFPT}$. Now, we group these different kinds of algorithms in complexity classes.

The class $\mathsf{EnumFPT}$/$\mathsf{DelayFPT}$/$\mathsf{IncFPT}$/$\mathsf{OutputFPT}$ is the class of all PEPs that admit an $\mathsf{FPT}$-enumeration/$\mathsf{DelayFPT}$-/$\mathsf{IncFPT}$-/$\mathsf{OutputFPT}$-algorithm.

The class $\mathsf{DelayFPT}$ captures a good notion of tractability for parameterized enumeration complexity. Creignou et al. [19] identified a multitude of problems that admit $\mathsf{DelayFPT}$ enumeration. Note that, due to Flum and Grohe ([15], Proposition 1.34) the class $\mathsf{FPT}$ can be characterized via runtimes of the form either $f(\kappa (x))·p(|x|)$ or $f(\kappa (x))+p(|x|)$ (as $a·b\le a^2+b^2$, for all $a,b\in \mathbb{N}$). Accordingly, this applies also to the introduced classes $\mathsf{DelayFPT}$, $\mathsf{IncFPT}$, and $\mathsf{OutputFPT}$.

3. Interleaving Hierarchies of Parameterized Incremental Delay

The previous observations raise the question of how $\mathsf{DelayFPT}$ relates to $\mathsf{IncFPT}$. In the classical enumeration world, this question has been partially answered by Capelli and Strozecki ([12], Proposition 16) for a weaker capped version of incremental polynomial time: $\mathsf{DelayP}⊊\mathsf{CapIncP}$ is true for the restriction to solution sets that do not necessarily obey the last two items of Definition 3 (they call this class $\mathrm{Enum}·\mathrm{F}$). Only for linear total time and polynomial space under this setting is the relation not completely understood, that is, the question how $\mathsf{DelayP}$ with polynomial space relates to ${\mathsf{CapIncP}}_1$ with polynomial space ([12], Open Problem 1, p. 10).

In the course of this chapter, it is shown that the relationship between the classical and the parameterized world is very close. Capelli and Strozecki approach the separation mentioned above through the classes ${\mathsf{CapIncP}}_a$ and prove a strict hierarchy of these classes. We lift this to the parameterized setting.

Definition 8

(Sliced Versions of Incremental FPT Delay, extending Definition 7). Let $E=(Q,\kappa ,\mathrm{Sol})$ be a PEP and $\mathcal{A}$ an enumeration algorithm for E. Then, algorithm $\mathcal{A}$ is

3′.

a ${\mathsf{CapIncFPT}}_a$-algorithm (for $a\in \mathbb{N}$) if there exists a computable function $t:\mathbb{N}\to \mathbb{N}$ and a polynomial p such that for every $x\in {\Sigma }^{*}$, $\mathcal{A}$ outputs i elements of $\mathrm{Sol}(x)$ in time $t(\kappa (x))·i^a·p(|x|)$ (for every $0\le i\le |\mathrm{Sol}(x)|$).

3″.

an ${\mathsf{IncFPT}}_a$-algorithm (for $a\in \mathbb{N}$) if there exists a computable function $t:\mathbb{N}\to \mathbb{N}$ and a polynomial p such that for every $x\in {\Sigma }^{*}$, $\mathcal{A}$ outputs $\mathrm{Sol}(x)$ and its i-th delay is at most $t(\kappa (x))·i^a·p(|x|)$.

Similarly, we define a hierarchy of classes ${\mathsf{CapIncFPT}}_a$ for every $a\in \mathbb{N}$ which consist of problems that admit an ${\mathsf{CapIncFPT}}_a$-algorithm. Moreover, $\mathsf{CapIncFPT}:={\bigcup }_{a\in \mathbb{N}}{\mathsf{CapIncFPT}}_a$.

Clearly, ${\bigcup }_{a\in \mathbb{N}}{\mathsf{IncFPT}}_a=\mathsf{IncFPT}$ and ${\mathsf{IncFPT}}_0=\mathsf{DelayFPT}$ by Definition 7 as the i-th delay then merely is $t(\kappa (x))·p(|x|)$, as $i^0=1$.

Usually, one utilizes a priority queue to store the already printed solutions as it allows for efficiently detecting duplicates. Nevertheless, it is unclear how to detect duplicates of solutions without storing them in the queue. Currently, it seems that the price of a “regular” (that is, polynomial) delay then is paid by the need for exponential space. Agreeing with Capelli and Strozecki ([12], Section 3), it seems very reasonable to see the difference of ${\mathsf{IncFPT}}_1$ and $\mathsf{DelayFPT}$ anchored in the presence of an exponential sized priority queue. However, relaxing this statement shows that the equivalence of incremental $\mathsf{FPT}$ delay and capped incremental $\mathsf{FPT}$-time is also true in the parameterized world. Similarly, as in the classical setting ([12], Proposition 12), the benefit of a structured delay can be reached with the exponential space of a priority queue. To lift the argumentation in the proof to the parameterized setting, one needs to keep track of the factors of the kind $t(\kappa (x))$ in the process. The remainder of the argumentation is the same.

Theorem 1.

For every $a\ge 0$, ${\mathsf{CapIncFPT}}_{a+1}={\mathsf{IncFPT}}_a$.

Proof. 

“⊇”: Let $E=(Q,\kappa ,\mathrm{Sol})$ be a PEP in ${\mathsf{IncFPT}}_a$ via an algorithm $\mathcal{A}$. Let $t:\mathbb{N}\to \mathbb{N}$ be a computable function and $p:\mathbb{N}\to \mathbb{N}$ be a polynomial as in Definition 8 (3″). For every $x\in Q$, algorithm $\mathcal{A}$ outputs i solutions with a running time bounded by

$$\begin{array}{c}\hfill \sum _{k=0}^{i}t(\kappa (x))·p(|x|)·k^a=t(\kappa (x))·p(|x|)·\sum _{k=0}^i{k}^a\le t(\kappa (x))·p(|x|)·(i+1)·i^a\\ \hfill \le 2·t(\kappa (x))·p(|x|)·i^{a+1}.\end{array}$$

Accordingly, we have that $E\in {\mathsf{CapIncFPT}}_{a+1}$.

“⊆”: Now consider a problem $E=(Q,\kappa ,\mathrm{Sol})\in {\mathsf{CapIncFPT}}_{a+1}$ via $\mathcal{A}$ enumerating i elements of $\mathrm{Sol}(x)$ in time $\le t(\kappa (x))i^{a+1}·p(|x|)$ for all $x\in Q$, for all $0\le i\le |\mathrm{Sol}(x)|$, and some computable function t (see Definition 8 (3′)). We show that enumerating $\mathrm{Sol}(x)$ can be achieved with an i-th delay of $O(t(\kappa (x))·p(|x|)·q(i)+s)$, where $q(i)={(i+1)}^{a+1}-i^{a+1}$ and s bounds the solution sizes (which is polynomially in the input length; w.l.o.g. let p be an upper bound for this polynomial). This means that we argue on the duration of the i-th delay, which summarizes the time needed to find the i-th solution and to print it. To reach this delay, one uses two counters: one for the steps of $\mathcal{A}$ (steps) and one for the solutions, initialized with value 1 (solindex). While simulating $\mathcal{A}$, the solutions are inserted into a priority queue $\mathcal{Q}$ instead of printing them. Eventually, the step counter reaches $t(\kappa (x))·p(|x|)·{\mathsf{solindex}}^{a+1}$. Then, the first element of $\mathcal{Q}$ is extracted, output, and $\mathsf{solindex}$ is incremented by one. In view of this, $\mathcal{A}$ computed solindex many solutions and prints the next one (or $\mathcal{A}$ already halted). Combining these observations leads to calculating the i-th delay:

$$\begin{array}{cc}\hfill & {O(t(\kappa (x))·p(|x|)·(i+1)}^{a+1}-t(\kappa (x))·p(|x|)·i^{a+1}+s)\hfill \\ \hfill =& O(t(\kappa (x))·p(|x|)·q(i)+p(|x|))\hfill \\ \hfill =& O(t(\kappa (x))·p(|x|)·i^a)(\mathrm{as}q(i)\in O(i^a))\hfill \end{array}$$

Clearly, this is a delay of the required form $t(\kappa (x))·p(|x|)·i^a$, and thus, $E\in {\mathsf{IncFPT}}_a$. □

Note that from the previous result, one can easily obtain the following corollary.

Corollary 2.

${\mathsf{CapIncFPT}}_1=\mathsf{DelayFPT}$ and $\mathsf{CapIncFPT}=\mathsf{IncFPT}$.

If one drops the restrictions 3. and 4. from Definition 3, then Capelli and Strozecki unconditionally show a strict hierarchy for the cap-classes via utilizing the well-known time hierarchy theorem [42]. Of course, this result transfers also to the parameterized world, that is, to the same generalization of ${\mathsf{CapIncFPT}}_a$. Nonetheless, it is unknown whether a similar hierarchy can be unconditionally shown for these classes as well as for ${\mathsf{IncFPT}}_a$.

Open Problem 1.Can a similar hierarchy be unconditionally shown for these classes as well as for ${\mathsf{IncFPT}}_a$?

This is a significant question of further research which is strengthened in the following section via connecting parameterized with classical enumeration complexity.

4. Connecting with Classical Enumeration Complexity

Capelli and Strozecki [12] ask whether a polynomial delay algorithm using exponential memory can be translated into an output polynomial or even incremental polynomial algorithm requiring only polynomial space. This question might imply a time–space tradeoff, that is, avoiding exponential space for a $\mathsf{DelayP}$-algorithm will yield the price of an increasing $\mathsf{IncP}$ delay. This remark perfectly reflects with what has been observed by Creignou et al. [20]. They noticed that outputting solutions ordered by their size seems to require exponential space in case one aims for $\mathsf{DelayFPT}$. Nonetheless, the mandatory order is a strong additional constraint which might weaken the evidence of that result substantially. As mentioned in the introduction, Meier and Reinbold [22] observed how a $\mathsf{DelayFPT}$ algorithm with exponential space of a specific problem is transformed into an $\mathsf{IncFPT}$ algorithm with polynomial space. These results emphasize what we strive for and why it is valuable to have such a connection between these two enumeration complexity fields. In this section, we prove that a collapse of $\mathsf{IncP}$ and $\mathsf{OutputP}$ implies $\mathsf{OutputFPT}$ collapsing to $\mathsf{IncFPT}$ and vice versa.

Capelli and Strozecki [12] investigated connections from enumeration complexity to function complexity classes of a specific type. The classes of interest contain many notable computational problems such as integer factoring, local optimization, or binary linear programming.

It is well known that function variants of classical complexity classes do not contain functions as members but relations instead. Accordingly, we formally identify languages $Q\subseteq {\Sigma }^{*}$ and their solution-space $\mathcal{S}\subseteq {\Sigma }^{*}$ with relations $\{(x,y)\mid y\in \mathrm{Sol}(x)\}$ and thereby extend the notation of PPs, EPs, and PEPs. Nevertheless, it is easy to see how to utilize a witness function f for a given language L such that $x\in L$ implies $f(x)=y$ for some y such that $A(x,y)$ is true (this means that $(x,y)\in A$ for the kind of relations mentioned before), and $f(x)=$“no” otherwise, in order to match the term “function complexity class” more adequately.

Definition 9.

We say that a relation $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ is polynomially balanced if $(x,y)\in A$ implies that $|y|\le p(|x|)$ for some polynomial p.

Recall that, for instances of a (P)EP E over $\Sigma$, the length of its solutions is polynomially bounded. Accordingly, the underlying relation $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ is polynomially balanced.

The following two definitions present four function complexity classes.

Definition 10

($\mathsf{F}\mathsf{P}$ and $\mathsf{F}\mathsf{NP}$). Let $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ be a binary and polynomially balanced relation.

• $A\in \mathsf{F}\mathsf{P}$ if there is a deterministic polynomial time algorithm that, given $x\in {\Sigma }^{*}$, can find some $y\in {\Sigma }^{*}$ such that $A(x,y)$ is true.
• $A\in \mathsf{F}\mathsf{NP}$ if there is a deterministic polynomial time algorithm that can determine whether $A(x,y)$ is true, given both x and y.

Definition 11

($\mathsf{F}(\mathsf{FPT})$ and $\mathsf{F}(\mathsf{para}$-$\mathsf{NP})$). Let $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ be a parameterized and polynomially balanced relation with parameterization κ.

• $A\in \mathsf{F}(\mathsf{FPT})$ if there exists a deterministic algorithm that, given $x\in {\Sigma }^{*}$, can find some $y\in {\Sigma }^{*}$ such that $A(x,y)$ is true and runs in time $f(\kappa (x))·p(|x|)$, where f is a computable function and p is a polynomial.
• $A\in \mathsf{F}(\mathsf{para}$-$\mathsf{NP})$ if there exists a deterministic algorithm that, given both x and y, can determine whether $A(x,y)$ is true and runs in time $f(\kappa (x))·p(|x|)$, where f is a computable function and p is a polynomial.

Note that the definition of $\mathsf{F}(\mathsf{para}$-$\mathsf{NP})$ follows the verifier characterization of precomputation on the parameter as observed in Corollary 1. Similarly to the classical decision class, $\mathsf{NP}$, the runtime has to be independent of the witness length $|y|$.

The next definition lifts the class $\mathsf{F}(\mathsf{NP}\cap \mathsf{co}\mathsf{NP})$ [23] to the parameterized setting. Notice that the class definition incorporates two special markers (called a and b)—similar as in the classical setting—to differentiate between the two types of witnesses.

Definition 12

($\mathsf{F}(\mathsf{para}$-$\mathsf{NP}\cap \mathsf{para}$-$\mathsf{co}\mathsf{NP})$). Given a language $L\subseteq {\Sigma }^{*}$, we say that $L\in \mathsf{F}(\mathsf{para}$-$\mathsf{NP}\cap \mathsf{para}$-$\mathsf{co}\mathsf{NP})$ if there exist two parameterized and polynomially balanced relations $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ and $B\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ with parameterizations κ and ${\kappa }^{\prime }$ as well as a nondeterministic algorithm N such that the following two properties are fulfilled.

• For each $x\in L$, either there exists a y with $(x,ay)\in A$, or there is a z with $(x,bz)\in B$, where $a\ne b$ are two special markers in Σ.
• Given $x\in {\Sigma }^{*}$, N can find either a y with $A(x,ay)$ or a z with $B(x,bz)$ in time $f(\kappa (x))·p(|x|)+g({\kappa }^{\prime }(x))·q(|x|)$, or state that such ones do not exist, where $p,q$ are polynomials and $f,g$ are computable functions.

The typical problems in $\mathsf{F}(\mathsf{para}$-$\mathsf{NP}\cap \mathsf{para}$-$\mathsf{co}\mathsf{NP})$ then ask for finding an appropriate witness (of ‘type’ either a or b) with respect to a given x. (

Table 1. Overview of function complexity classes. In the machine column, ‘det.’/‘nond.’ abbreviates ‘deterministic’/‘nondeterministic’. In the runtime column, p and q are polynomials, f and g are two computable functions, $\kappa$ is the parameterization of A, ${\kappa }^{\prime }$ is the parameterization of B, and x is the input.

Class	Machine	Runtime	Constraints
$\mathsf{F}\mathsf{P}$	det.	$p(|x|)$	find y such that $A(x,y)$
$\mathsf{F}\mathsf{NP}$	nond.	$p(|x|)$	guess y such that $A(x,y)$
$\mathsf{TF}\mathsf{NP}$	nond.	$p(|x|)$	guess y such that $A(x,y)$, A is total
$\mathsf{F}(\mathsf{FPT})$	det.	$f(\kappa (x))·p(|x|)$	find y such that $A(x,y)$
$\mathsf{F}(\mathsf{para}$-$\mathsf{NP})$	nond.	$f(\kappa (x))·p(|x|)$	guess y such that $A(x,y)$
$\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$	nond.	$f(\kappa (x))·p(|x|)$	guess y such that $A(x,y)$, A is total
$\mathsf{F}(\mathsf{para}$-$\mathsf{NP}\cap \mathsf{para}$-$\mathsf{co}\mathsf{NP})$	nond.	$f(\kappa (x))·p(|x|)+$$g({\kappa }^{\prime }(x))·q(|x|)$	either find y with $A(x,ay)$ or z with $B(x,bz)$

)

In 1994, Bellare and Goldwasser [43] investigated functional versions of $\mathsf{NP}$ problems. They observed that under standard complexity-theoretic assumptions (deterministic doubly exponential time is different from nondeterministic doubly exponential time), such functional variants are not self-reducible (as the decision variant is). Here, a problem is self-reducible means that one constructs a witness in a bit-wise fashion, given an oracle for that problem. Bellare and Goldwasser noticed that these functional versions are harder than their corresponding decision variants.

A binary relation $R\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ is said to be total if for every $x\in {\Sigma }^{*}$ there exists a $y\in {\Sigma }^{*}$ such that $(x,y)\in R$.

Definition 13

(Total function complexity classes). $\mathsf{TF}\mathsf{NP}$ (resp., $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$) is the restriction of $\mathsf{F}\mathsf{NP}$ (resp., $\mathsf{F}(\mathsf{para}$-$\mathsf{NP})$) to total relations.

The two previously defined classes are promise classes in the sense that the existence of a witness y with $A(x,y)$ is guaranteed. Furthermore, defining a class $\mathsf{TF}(\mathsf{P})$ or $\mathsf{TF}(\mathsf{FPT})$ is not meaningful as it is known that $\mathsf{F}\mathsf{P}\subseteq \mathsf{TF}\mathsf{NP}$ (see, e.g., the work of Johnson et al. ([44], Lemma 3) showing that $\mathsf{F}\mathsf{P}$ is contained in $\mathsf{PLS}$, polynomial local search, which is contained in $\mathsf{TF}\mathsf{NP}$ by Megiddo and Papadimitriou ([23], p. 319). Similar arguments apply to $\mathsf{F}(\mathsf{FPT})\subseteq \mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$).

Now, we can define a generic (parameterized) search and a generic (parameterized) enumeration problem. Note that the parameter is only relevant for the parameterized counterpart named in brackets.

Problem:	($\mathsf{para}$-AnotherSolA), where $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$
Input:	$x\in {\Sigma }^{*}$, $S\subseteq {\Sigma }^{*}$.
Parameter:	$\kappa :{\Sigma }^{*}\to \mathbb{N}$.
Task:	output y in $Sol(x)\backslash S$, or answer $S\supseteq \mathrm{Sol}(x)$.

Problem:	($\mathsf{para}$-)Enum-A, where $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$
Input:	$x\in {\Sigma }^{*}$.
Parameter:	$\kappa :{\Sigma }^{*}\to \mathbb{N}$.
Output:	output all y with $A(x,y)$.

The two results of Capelli and Strozecki ([12], Propositions 7 and 9) which are crucial in the course of this section are restated in the following.

Proposition 3

([12], Proposition 7). Let $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ be a binary relation such that, given $x\in {\Sigma }^{*}$, one can find a y with $A(x,y)$ in deterministic polynomial time. Then the following is true: AnotherSol_A ∈ $\mathsf{F}\mathsf{P}$ if and only if Enum-$A\in \mathsf{CapIncP}$.

Proposition 4

([12], Proposition 9). $\mathsf{TF}\mathsf{NP}=\mathsf{F}\mathsf{P}$ if and only if $\mathsf{OutputP}=\mathsf{CapIncP}$.

In 1991, Megiddo and Papadimitriou studied the complexity class $\mathsf{TF}\mathsf{NP}$ [23]. In a recent investigation, Goldberg and Papadimitriou introduced a rich theory around this complexity class that also features several aspects of proof theory [24]. Megiddo and Papadimitriou prove that the classes $\mathsf{F}(\mathsf{NP}\cap \mathsf{co}\mathsf{NP})$ and $\mathsf{TF}\mathsf{NP}$ coincide. Their arguments are easily lifted to the parameterized setting.

Theorem 2.

$\mathsf{F}(\mathsf{para}$-$\mathsf{NP}\cap \mathsf{para}$-$\mathsf{co}\mathsf{NP})=\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$.

Proof. 

We reformulate the classical proofs of Megiddo and Papadimitriou [23].

“⊆”: By definition of the class $\mathsf{F}(\mathsf{para}$-$\mathsf{NP}\cap \mathsf{para}$-$\mathsf{co}\mathsf{NP})$, either there exists a y with $(x,ay)\in A$, or there is a z with $(x,bz)\in B$. As a result, the mapping $(A,B)\mapsto A\cup B$ suffices and $A\cup B$ is total as either of the two witnesses always exists (see Definition 12). Thus, one just needs to guess which of A or B to choose.

“⊇”: the mapping from the total relation A to $(A,\varnothing )$ meets the requirements of $\mathsf{F}(\mathsf{para}$-$\mathsf{NP}\cap \mathsf{para}$-$\mathsf{co}\mathsf{NP})$ as only one type of witnesses is needed, and for every x, there is a y such that $(x,y)\in A$ as A is total by assumption. □

For the following Lemma 1 (which is the parameterized pendant of Proposition 3) and theorem, we follow the argumentation in the proofs of the classical results (Propositions 3 and 4). They underline the interplay between search and enumeration.

Lemma 1.

Let $A\subseteq {\Sigma }^{*}$ be a parameterized problem with parameterization κ. Then,$\mathsf{para}$-AnotherSol_A ∈ $\mathsf{F}(\mathsf{FPT})$ if and only if $\mathsf{para}$-Enum-$A\in \mathsf{CapIncFPT}$.

Proof. 

“⇒”: Let $\mathsf{para}$-AnotherSol_A ∈ $\mathsf{F}(\mathsf{FPT})$ via some algorithm $\mathcal{A}$. Algorithm 1 shows that $\mathsf{para}$-Enum-$A\in \mathsf{CapIncFPT}$.

The runtime of each step is $f(\kappa (x))·p(|x|,|S|)$ for some polynomial p and some computable function f. Consequently, this shows that $\mathsf{para}$-Enum-$A\in \mathsf{CapIncFPT}$.

“⇐”: Let $\mathsf{para}$-Enum-$A\in \mathsf{CapIncFPT}$. Then, there exists a parameterized enumeration algorithm $\mathcal{A}$ that, given input $x\in {\Sigma }^{*}$, outputs $i\le \mathrm{Sol}(x)$ elements in a runtime of $f(\kappa (x))·i^a·p(|x|)$ for some computable function f, $a\in \mathbb{N}$, and a polynomial p.

Now, we explain how to compute $\mathsf{para}$-AnotherSol_A in fpt-time. Given $(x,S)$, simulate $\mathcal{A}$ for $f(\kappa (x))·{(|S|+1)}^a·p(|x|)$ steps. If the simulation successfully halts, then $\mathrm{Sol}(x)$ is completely output. Just search a $y\in \mathrm{Sol}(x)\backslash S$ or output “$S\supseteq \mathrm{Sol}(x)$”. Otherwise, if $\mathcal{A}$ did not halt, then it did output at least $|S|+1$ different elements. Finally, we just compute $\mathrm{Sol}(x)\backslash S$ and print a new element. □

Algorithm 1: Algorithm showing $\mathsf{para}$-Enum-$A\in \mathsf{CapIncFPT}$.

The next theorem translates the result of Proposition 4 from classical enumeration complexity to the parameterized setting. It shows the first connection of parameterized enumeration to parameterized function complexity.

Theorem 3.

$\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})=\mathsf{F}(\mathsf{FPT})$ if and only if $\mathsf{OutputFPT}=\mathsf{CapIncFPT}$.

Proof. 

“⇐”: Let $A\in \mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$ be a parameterized language over ${\Sigma }^{*}\times {\Sigma }^{*}$ with parameterization $\kappa$. Furthermore, let M denote the nondeterministic algorithm that guesses the witnesses y and then verifies with the deterministic algorithm as in Definition 11. Additionally, denote the running time of M by $g(\kappa (x))·p(|x|)$ for a polynomial p, a computable function g, and an input x. Now, define the relation $C\subseteq {\Sigma }^{*}\times \left\{y\#w\mid y\in {\Sigma }^{*},w\in {\{0,1\}}^{*}\right\}$, where $\#\notin \Sigma$, such that

$$\begin{array}{c}\hfill C(x,y\#w)\mathrm{if}\mathrm{and}\mathrm{only}\mathrm{if}A(x,y)\mathrm{and}|w|\le p(|x|).\end{array}$$

Then, for each x there exists $y\#w$ such that $C(x,y\#w)$ is true by the definition of the class $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$. Moreover, via padding, for each x, there exist at least $2^{p(|x|)}$ solutions z such that $C(x,z)$ is true; in particular, z is of the form $y\#w$ such that $A(x,y)$ is true. Notice that the total length of $y\#w$ is bounded by $g(\kappa (x))·p(|x|)+p(|x|)+1$ as y already has the length constraint of $g(\kappa (x))·p(|x|)$ by the $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$ requirement. By construction, the trivial brute-force enumeration algorithm checking all $y\#w$ is in time $g(\kappa (x))·p(|x|)$ for every element of $\mathrm{Sol}(x)$. Accordingly, this gives $\mathsf{para}$-Enum-$C\in \mathsf{OutputFPT}$ as the runtime for $\mathsf{OutputFPT}$ algorithms encompasses $|\mathrm{Sol}(x)|$ as a factor.

Then, $\mathsf{para}$-Enum-$C\in \mathsf{CapIncFPT}$ and the first $y\#w$ is output in time $g(\kappa (x))·p(|x|)$. Since A was arbitrary, we conclude with $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})=\mathsf{F}(\mathsf{FPT})$ (as $\mathsf{F}(\mathsf{FPT})\subseteq \mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$ by definition).

“⇒”: Consider a problem $\mathsf{para}$-Enum-$A\in \mathsf{OutputFPT}$ with $\mathsf{para}$-Enum-$A=(Q,\kappa ,\mathrm{Sol})$. For every $x\in Q$ and $S\subseteq \mathrm{Sol}(x)$ let $D((x,S),y)$ be true if and only if either ($y\in \mathrm{Sol}(x)\backslash S$) or ($y=\#$ and $S\supseteq \mathrm{Sol}(x)$). Then, $D\in \mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$:

• D is total by construction,
• as $\mathsf{para}$-Enum-$A$ is a PEP, there exists a polynomial q such that for every solution $y\in \mathrm{Sol}(x)$ we have that $|y|\le q(|x|)$, and
• finally, we need to show that $D((x,S),y)$ can be verified in deterministic time $f(\kappa (x))·p(|x|,|S|,|y|)$ for a computable function f and a polynomial p.

  Case $\mathbf{y}\ne \#$:

  $D((x,S),y)$ is true if and only if $y\in \mathrm{Sol}(x)\backslash S$. This requires testing whether $y\notin S$ and $y\in \mathrm{Sol}(x)$. Both can be tested in polynomial time: $p(|y|,|S|)$, respectively, $p(|x|)$ which follows from Definition 7 (4.).

  Case $\mathbf{y}=\#$:

  $D((x,S),y)$ is true if and only if $S\supseteq \mathrm{Sol}(x)$. As $\mathsf{para}$-Enum-$A\in \mathsf{OutputFPT}$, there is a deterministic algorithm $\mathcal{A}$ outputting $\mathrm{Sol}(x)$ in $f(\kappa (x))·p(|x|,|\mathrm{Sol}(x)|)$ steps. Now, run $\mathcal{A}$ for at most $f(\kappa (x))·p(|x|,|S|)$ steps. Then, finishing within this steps-bound implies that $\mathrm{Sol}(x)$ is completely generated, and we merely check $S\supseteq \mathrm{Sol}(x)$ in time polynomial in $|S|$. If $\mathcal{A}$ did not halt within the steps-bound, we can deduce $|\mathrm{Sol}(x)|>|S|$. Accordingly, $S\neg \supseteq \mathrm{Sol}(x)$ follows and $D((x,S),y)$ is not true.

As $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})=\mathsf{F}(\mathsf{FPT})$ is true by precondition, given a tuple $(x,S)$, we either can compute a y with $y\in \mathrm{Sol}(x)\backslash S$ or decide there is none (and then set $y=\#$) in time $f(\kappa (x))·p(|x|,|S|,|y|)$. Accordingly, $\mathsf{para}$-AnotherSol_A is in $\mathsf{F}(\mathsf{FPT})$ and, by applying Lemma 1, we get $\mathsf{para}$-Enum-$A$ is in $\mathsf{CapIncFPT}$. This settles that $\mathsf{OutputFPT}=\mathsf{CapIncFPT}$ and concludes the proof. □

The next theorem connects a collapse in the classical function world to a collapse in the parameterized function world. It witnesses the first connection between a collapse in classical and one in parameterized function complexity.

Theorem 4.

$\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})=\mathsf{F}(\mathsf{FPT})$ if and only if $\mathsf{TF}\mathsf{NP}=\mathsf{F}\mathsf{P}$.

Proof. 

Let us start with the easy direction.

“⇒”: Let $A\subseteq {\Sigma }^{*}\times {\Sigma }^{*}$ be a total relation in $\mathsf{TF}\mathsf{NP}$. By definition of $\mathsf{TF}\mathsf{NP}$ and $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$, $(A,{\kappa }_0)\in \mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$, where ${\kappa }_0$ is the trivial parameterization assigning to each $x\in {\Sigma }^{*}$ the zero 0. Since $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})=\mathsf{F}(\mathsf{FPT})$, there exists a computable function $f:\mathbb{N}\to \mathbb{N}$, a polynomial p, and a deterministic algorithm $\mathcal{A}$, that, given the input $x\in {\Sigma }^{*}$, outputs some $y\in {\Sigma }^{*}$ such that $A(x,y)$ in time $f({\kappa }_0(x))·p(x)$. As ${\kappa }_0(x)=0$ for each x, $f({\kappa }_0(x))=f(0)\in \mathbb{N}$ for each x and $\mathcal{A}$ runs in polynomial time. Accordingly, we have $A\in \mathsf{F}\mathsf{P}$ and thereby $\mathsf{F}\mathsf{P}=\mathsf{TF}\mathsf{NP}$ as A was chosen arbitrarily.

“⇐”: Choose some $B\in \mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$ via the nondeterministic machine M running in time $f(\kappa (x))·p(|x|)$ for a polynomial p, a computable function f, a parameterization $\kappa$, and an input x. By Proposition 1, we know that there exists a computable function $\pi :{\Sigma }^{*}\to {\Sigma }^{*}$ and a problem $B^{\prime }\subseteq {\Sigma }^{*}\times {\Sigma }^{*}\times {\Sigma }^{*}$ such that $B^{\prime }\in \mathsf{F}\mathsf{NP}$ and the following is true: for all instances $x\in {\Sigma }^{*}$ and all solutions $y\in {\Sigma }^{*}$, we have that $(x,y)\in B$ if and only if $\left((x,\pi (\kappa (x)),y\right)\in B^{\prime }$.

As B is total, $B^{\prime }$ is total with respect to the third argument as well. It follows by assumption that $B^{\prime }$ is also in $\mathsf{F}\mathsf{P}$ via some deterministic machine $M^{\prime }$ having a runtime bounded by a polynomial q in the input length. Accordingly, we can define a deterministic machine $\tilde{M}$ for B which, given input $x\in {\Sigma }^{*}$, computes $\pi (\kappa (x))$, then simulates $M^{\prime }$ on $(x,\pi (\kappa (x)))$, and runs in time

$$\begin{array}{c}\hfill f_{\pi }(\kappa (x))+q(|\pi (\kappa (x))|,|x|),\end{array}$$

(1)

where $f_{\pi }:{\Sigma }^{*}\to \mathbb{N}$ is a computable function that estimates the runtime of computing $\pi (\kappa (x))$. Clearly, Equation (1) is an fpt-runtime witnessing $B\in \mathsf{F}(\mathsf{FPT})$. Accordingly, we can deduce that $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})=\mathsf{F}(\mathsf{FPT})$, as B was chosen arbitrarily. □

Combining Theorem 3 with Theorem 4 and finally Proposition 4 connects the parameterized enumeration world with the classical enumeration world. The following corollary summarizes deducible connections of parameterized enumeration to classical enumeration, parameterized function complexity, classical function complexity, and decision complexity. This means that a collapse of $\mathsf{OutputFPT}$ to $\mathsf{CapIncFPT}$ would yield a collapse of $\mathsf{TF}\mathsf{NP}$ to $\mathsf{F}\mathsf{P}$ (Proposition 4) and as well as of $\mathsf{P}$ to $\mathsf{NP}\cap \mathsf{co}\mathsf{NP}$ (due to $\mathsf{TF}\mathsf{NP}=\mathsf{F}(\mathsf{NP}\cap \mathsf{co}\mathsf{NP})$ [23]).

Corollary 3.

The following collapses are equivalent:

• $\mathsf{OutputFPT}=\mathsf{CapIncFPT}$
• $\mathsf{OutputP}=\mathsf{CapIncP}$
• $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})=\mathsf{F}(\mathsf{FPT})$
• $\mathsf{TF}\mathsf{NP}=\mathsf{F}\mathsf{P}$
• $\mathsf{P}=\mathsf{NP}\cap \mathsf{co}\mathsf{NP}$

If one does not consider space requirements—which is usually the case for these classes—we can deduce the following corollary by applying Corollary 2 and Proposition 2.

Corollary 4.

Without space requirements, we have that $\mathsf{OutputFPT}=\mathsf{IncFPT}$ if and only if $\mathsf{OutputP}=\mathsf{IncP}$.

Now, we have seen that the observations made by Capelli and Strozecki [12] can be directly transferred to the parameterized setting. In cryptography, one-way functions are functions that are easily (in polynomial time) to compute but hard to invert (often, this means either it requires exponential time to invert the function, or, in a probabilistic model, the search space is of exponential size wherefore the success probability to invert the function is very low). A good introduction to this topic is given by Talbot and Welsh [37]. As a result of Corollary 3 together with Corollary 4, for instance, the existence of one-way functions would separate $\mathsf{OutputFPT}$ from $\mathsf{IncFPT}$ as well.

5. Conclusions and Outlook

We presented the first connection of parameterized enumeration to classical enumeration by showing that a collapse of $\mathsf{OutputFPT}$ to $\mathsf{IncFPT}$ implies collapsing $\mathsf{OutputP}$ to $\mathsf{CapIncP}$ and vice versa. While proving this result, we showed equivalences of collapses of parameterized function classes developed in this paper to collapses of classical function classes. In particular, we proved that $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})=\mathsf{F}(\mathsf{FPT})$ if and only if $\mathsf{TF}\mathsf{NP}=\mathsf{F}\mathsf{P}$ (Theorem 4). The function complexity class $\mathsf{TF}\mathsf{NP}$, which has $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$ as its parameterized counterpart, contains significant cryptography-related problems such as factoring. Furthermore, we studied a parameterized incremental $\mathsf{FPT}$ time enumeration hierarchy on the level of exponent slices (Definition 8) and observed that ${\mathsf{CapIncFPT}}_1=\mathsf{DelayFPT}$ (Corollary 2). Additionally, an interleaving of the two hierarchies, ${\mathsf{IncFPT}}_a$ and ${\mathsf{CapIncFPT}}_a$, has been shown (Theorem 1). The results of this paper underline that parameterized enumeration complexity is an area worth studies, as there are deep connections to its classical counterpart.

Future research should build on these classes to unveil the presence of exponential space in this setting and give a definite answer to the observed time–space tradeoffs of $\mathsf{IncFPT}$ versus $\mathsf{DelayFPT}$. Can the hierarchy ${\mathsf{IncFPT}}_a$ introduced and studied in Section 3, be shown strict under similar conditions as Capelli and Strozecki were able to prove (they used the exponential time hypothesis)? Moreover, it would be engaging to study connections from parameterized enumeration to proof theory via the work of Goldberg and Papadimitriou [24]. We want to close with the question of whether there exist intermediate natural problems between $\mathsf{F}(\mathsf{FPT})$ and $\mathsf{TF}(\mathsf{para}$-$\mathsf{NP})$ which are relevant in some area beyond trivial parameterization ${\kappa }_{\mathrm{one}}(x)=1$.