# Incremental FPT Delay
## 4 Connecting with Classical Enumeration Complexity
By Proposition 1, we know that there exists a computable function \(\pi\colon\Sigma^{*}\to\Sigma^{*}\) and a problem \(B^{\prime}\subseteq\Sigma^{*}\times\Sigma^{*}\times\Sigma^{*}\) such that \(B^{\prime}\in\mathsf{FNP}\) 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 \(\big{(}(x,\pi(\kappa(x)),y)\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{FP}\) 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 \(\widetilde{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  
\[f_{\pi}(\kappa(x))+q(|\pi(\kappa(x))|,|x|), \tag{1}\]  
where \(f_{\pi}\colon\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}\) toCaplncFPT would yield a collapse of \(\mathsf{TFNP}\) to \(\mathsf{FP}\) (Proposition 4) and as well as of \(\mathsf{P}\) to \(\mathsf{NP}\cap\mathsf{coNP}\) (due to \(\mathsf{TFNP}=\mathsf{F}(\mathsf{NP}\cap\mathsf{coNP})\)[23]). Corollary 3: _The following collapses are equivalent:_  
* \(\mathsf{OutputFPT}=\mathsf{CaplncFPT}\)__
* \(\mathsf{OutputP}=\mathsf{CaplncP}\)__
* \(\mathsf{TF}(\mathsf{para}\text{-}\mathsf{NP})=\mathsf{F}(\mathsf{FPT})\)__
* \(\mathsf{TFNP}=\mathsf{FP}\)__
* \(\mathsf{P}=\mathsf{NP}\cap\mathsf{coNP}\)__  
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 [PERSON] and [PERSON] [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 [PERSON] and [PERSON] [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.