# Incremental FPT Delay
## 4 Connecting with Classical Enumeration Complexity
\begin{table}
\begin{tabular}{l l l l} \hline \hline
**Class** & **Machine** & **Runtime** & **Constraints** \\ \hline \(\mathsf{FP}\) & det. & \(p(|x|)\) & find \(y\) such that \(A(x,y)\) \\ \(\mathsf{FNP}\) & nond. & \(p(|x|)\) & guess \(y\) such that \(A(x,y)\) \\ \(\mathsf{TFNP}\) & nond. & \(p(|x|)\) & guess \(y\) such that \(A(x,y)\), \(A\) is total \\ \(\mathsf{F}(\mathsf{FPT})\) & det. & \(f(\kappa(x))\cdot p(|x|)\) & find \(y\) such that \(A(x,y)\) \\ \(\mathsf{F}(\mathsf{para-NP})\) & nond. & \(f(\kappa(x))\cdot p(|x|)\) & guess \(y\) such that \(A(x,y)\) \\ \(\mathsf{TF}(\mathsf{para-NP})\) & nond. & \(f(\kappa(x))\cdot p(|x|)\) & guess \(y\) such that \(A(x,y)\), \(A\) is total \\ \(\mathsf{F}(\mathsf{para-NP}\cap\mathsf{para-coNP})\) & nond. & \(f(\kappa(x))\cdot p(|x|)+\) & either find \(y\) with \(A(x,ay)\) or \(z\) with \(B(x,bz)\) \\  & & \(g(\kappa^{\prime}(x))\cdot q(|x|)\) & \\ \hline \hline \end{tabular}
\end{table} 
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. The two results of [PERSON] and [PERSON] ([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: \(\textsc{AnotherSol}_{A}\in\mathsf{FP}\) if and only if \(\textsc{Enum-}A\in\mathsf{CapIncP}\)._  
Proposition 4 ([12], Proposition 9): \(\mathsf{TFNP}=\mathsf{FP}\) _if and only if \(\mathsf{OutputP}=\mathsf{CapIncP}\)._  
In 1991, [PERSON] and [PERSON] studied the complexity class \(\mathsf{TFNP}\)[23]. In a recent investigation, [PERSON] and [PERSON] introduced a rich theory around this complexity class that also features several aspects of proof theory [24]. [PERSON] and [PERSON] prove that the classes \(\mathsf{F}(\mathsf{NP}\cap\mathsf{coNP})\) and \(\mathsf{TFNP}\) coincide. Their arguments are easily lifted to the parameterized setting. Theorem 2: \(\mathsf{F}(\mathsf{para-NP}\cap\mathsf{para-coNP})=\mathsf{TF}(\mathsf{para- NP})\)_._  
Proof: We reformulate the classical proofs of [PERSON] and [PERSON] [23]. \"\(\subseteq\)\": By definition of the class \(\mathsf{F}(\mathsf{para-NP}\cap\mathsf{para-coNP})\), 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. \"\(\supseteq\)\": the mapping from the total relation \(A\) to \((A,\emptyset)\) meets the requirements of \(\mathsf{F}(\mathsf{para-NP}\cap\mathsf{para-coNP})\) 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 \(\kappa\). Then, \(\mathsf{para-AnotherSol}_{A}\in\mathsf{F}(\mathsf{FPT})\) if and only if \(\mathsf{para-Enum-}A\in\mathsf{CapIncFPT}\)._  
Proof: \"\(\Rightarrow\)\": Let \(\mathsf{para-AnotherSol}_{A}\in\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))\cdot p(|x|,|S|)\) for some polynomial \(p\) and some computable function \(f\).