# Incremental FPT Delay
## 4 Connecting with Classical Enumeration Complexity
\(D\) is total by construction,
2. as \(\mathsf{para}\)-\(\textsc{Enum}\)-\(A\) is a PEP, there exists a polynomial \(q\) such that for every solution \(y\in\mathrm{Sol}(x)\) we have that \(|y|\leq q(|x|)\), and
3. finally, we need to show that \(D((x,S),y)\) can be verified in deterministic time \(f(\kappa(x))\cdot p(|x|,|S|,|y|)\) for a computable function \(f\) and a polynomial \(p\). **Case \(y\
eq\#\):**: \(D((x,S),y)\) is true if and only if \(y\in\operatorname{Sol}(x)\setminus S\). This requires testing whether \(y\
otin S\) and \(y\in\operatorname{Sol}(x)\). Both can be tested in polynomial time: \(p(|y|,|S|)\), respectively, \(p(|x|)\) which follows from Definition 7 (4.). **Case \(y=\#\):**: \(D((x,S),y)\) is true if and only if \(S\supseteq\operatorname{Sol}(x)\). As \(\mathsf{para}\)-\(\mathsf{Enum}\)-\(\mathsf{A}\in\mathsf{OutputFPT}\), there is a deterministic algorithm \(\mathcal{A}\) outputting \(\operatorname{Sol}(x)\) in \(f(\kappa(x))\cdot p(|x|,|\operatorname{Sol}(x)|)\) steps. Now, run \(\mathcal{A}\) for at most \(f(\kappa(x))\cdot p(|x|,|S|)\) steps. Then, finishing within this steps-bound implies that \(\operatorname{Sol}(x)\) is completely generated, and we merely check \(S\supseteq\operatorname{Sol}(x)\) in time polynomial in \(|S|\). If \(\mathcal{A}\) did not halt within the steps-bound, we can deduce \(|\operatorname{Sol}(x)|>|S|\). Accordingly, \(S\
ot\supseteq\operatorname{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\operatorname{Sol}(x)\setminus S\) or decide there is none (and then set \(y=\#\)) in time \(f(\kappa(x))\cdot p(|x|,|S|,|y|)\). Accordingly, \(\mathsf{para}\)-\(\mathsf{AnotherSOL}_{A}\) is in \(\mathsf{F}(\mathsf{FPT})\) and, by applying Lemma 1, we get \(\mathsf{para}\)-\(\mathsf{Enum}\)-\(\mathsf{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{TFNP}=\mathsf{FP}\)._  
Proof: Let us start with the easy direction. \"\(\Rightarrow\)\": Let \(A\subseteq\Sigma^{*}\times\Sigma^{*}\) be a total relation in \(\mathsf{TFNP}\). By definition of \(\mathsf{TFNP}\) 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\colon\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))\cdot 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{FP}\) and thereby \(\mathsf{FP}=\mathsf{TFNP}\) as \(A\) was chosen arbitrarily. \"\(\Leftarrow\)\": Choose some \(B\in\mathsf{TF}(\mathsf{para}\)-\(\mathsf{NP})\) via the nondeterministic machine \(M\) running in time \(f(\kappa(x))\cdot p(|x|)\) for a polynomial \(p\), a computable function \(f\), a parameterization \(\kappa\), and an input \(x\).