# Incremental FPT Delay
## 4 Connecting with Classical Enumeration Complexity  
[PERSON] and [PERSON] [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 spacefor a DelayP-algorithm will yield the price of an increasing IncP delay. This remark perfectly reflects with what has been observed by [PERSON] et al. (2018). They noticed that outputting solutions ordered by their size seems to require exponential space in case one aims for DelayFPT. Nonetheless, the mandatory order is a strong additional constraint which might weaken the evidence of that result substantially. As mentioned in the introduction, [PERSON] and [PERSON] (2018) observed how a DelayFPT algorithm with exponential space of a specific problem is transformed into an 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 IncP and OutputP implies OutputFPT collapsing to IncFPT and vice versa. [PERSON] and [PERSON] (2018) 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\text{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. We say that a relation \(A\subseteq\Sigma^{*}\times\Sigma^{*}\) is _polynomially balanced_ if \((x,y)\in A\) implies that \(|y|\leq 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. [FP and FNP] Let \(A\subseteq\Sigma^{*}\times\Sigma^{*}\) be a binary and polynomially balanced relation. * \(A\in\mathsf{FP}\) 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{FNP}\) if there is a deterministic polynomial time algorithm that can determine whether \(A(x,y)\) is true, given both \(x\) and \(y\). [F\((\mathsf{FPT})\) and \(\mathsf{F}(\mathsf{para}\text{-}\mathsf{NP})\)] Let \(A\subseteq\Sigma^{*}\times\Sigma^{*}\) be a parameterized and polynomially balanced relation with parameterization \(\kappa\). * \(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))\cdot p(|x|)\), where \(f\) is a computable function and \(p\) is a polynomial. * \(A\in\mathsf{F}(\mathsf{para}\text{-}\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))\cdot p(|x|)\), where \(f\) is a computable function and \(p\) is a polynomial. Note that the definition of \(\mathsf{F}(\mathsf{para}\text{-}\mathsf{NP})\) follows the verifier characterization of precomputation on the parameter as observed in Corollary 1.