# Incremental FPT Delay
## 4 Connecting with Classical Enumeration Complexity
Consequently, this shows that \(\mathsf{para-Enum-}A\in\mathsf{CapIncFPT}\). \"\(\Leftarrow\)\": 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\leq\mathsf{Sol}(x)\) elements in a runtime of \(f(\kappa(x))\cdot i^{a}\cdot p(|x|)\) for some computable function \(f\), \(a\in\mathbb{N}\), and a polynomial \(p\). Now, we explain how to compute \(\mathsf{para}\)-\(\textsc{AnotherSol}_{A}\) in fpt-time. Given \((x,S)\), simulate \(\mathcal{A}\) for \(f(\kappa(x))\cdot(|S|+1)^{a}\cdot p(|x|)\) steps. If the simulation successfully halts, then \(\mathrm{Sol}(x)\) is completely output. Just search a \(y\in\mathrm{Sol}(x)\setminus 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)\setminus S\) and print a new element. ```
1\(S\leftarrow\emptyset\);
2 repeat
3\(y\leftarrow\mathcal{A}(x,S)\);
4\(S\gets S\cup\{y\}\);
5 print\(y\);
6
7 until\(S=A(x)\);
```  
**Algorithm 1**Algorithm showing \(\mathsf{para}\)-\(\textsc{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: \"\(\Leftarrow\)\": 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))\cdot p(|x|)\) for a polynomial \(p\), a computable function \(g\), and an input \(x\). Now, define the relation \(C\subseteq\Sigma^{*}\times\{y\#w\mid y\in\Sigma^{*},w\in\{0,1\}^{*}\}\), where \(\#\
otin\Sigma\), such that  
\[C(x,y\#w)\text{ if and only if }A(x,y)\text{ and }|w|\leq p(|x|).\]  
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))\cdot p(|x|)+p(|x|)+1\) as \(y\) already has the length constraint of \(g(\kappa(x))\cdot 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))\cdot p(|x|)\) for every element of \(\mathrm{Sol}(x)\). Accordingly, this gives \(\mathsf{para}\)-\(\textsc{Enum}\)-\(\textsc{C}\in\mathsf{OutputFPT}\) as the runtime for \(\mathsf{OutputFPT}\) algorithms encompasses \(|\mathrm{Sol}(x)|\) as a factor. Then, \(\mathsf{para}\)-\(\textsc{Enum}\)-\(\textsc{C}\in\mathsf{CapIncFPT}\) and the first \(y\#w\) is output in time \(g(\kappa(x))\cdot 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). \"\(\Rightarrow\)\": Consider a problem \(\mathsf{para}\)-\(\textsc{Enum}\)-\(A\in\mathsf{OutputFPT}\) with \(\mathsf{para}\)-\(\textsc{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)\setminus S)\) or \((y=\#\) and \(S\supseteq\mathrm{Sol}(x))\). Then, \(D\in\mathsf{TF}(\mathsf{para}\)-\(\mathsf{NP})\):  
1.