# Incremental FPT Delay
## 3 Interleaving Hierarchies of Parameterized Incremental Delay
Let \(t\colon\mathbb{N}\to\mathbb{N}\) be a computable function and \(p\colon\mathbb{N}\to\mathbb{N}\) be a polynomial as in Definition 8 (3\"). For every \(x\in Q\), algorithm \(\mathcal{A}\) outputs \(i\) solutions with a running time bounded by  
\[\sum_{k=0}^{i}t(\kappa(x))\cdot p(|x|)\cdot k^{a}=t(\kappa(x)) \cdot p(|x|)\cdot\sum_{k=0}^{i}k^{a} \leq t(\kappa(x))\cdot p(|x|)\cdot(i+1)\cdot i^{a}\] \[\leq 2\cdot t(\kappa(x))\cdot p(|x|)\cdot i^{a+1}.\]  
Accordingly, we have that \(E\in\text{CapIncFPT}_{a+1}\). \"\(\subseteq\)\": Now consider a problem \(E=(Q,\kappa,\text{Sol})\in\text{CapIncFPT}_{a+1}\) via \(\mathcal{A}\) enumerating \(i\) elements of \(\text{Sol}(x)\) in time \(\leq t(\kappa(x))i^{a+1}\cdot p(|x|)\) for all \(x\in Q\), for all \(0\leq i\leq|\text{Sol}(x)|\), and some computable function \(t\) (see Definition 8 (3\")). We show that enumerating \(\text{Sol}(x)\) can be achieved with an \(i\)-th delay of \(O(t(\kappa(x))\cdot p(|x|)\cdot q(i)+s)\), where \(q(i)=(i+1)^{a+1}-i^{a+1}\) and \(s\) bounds the solution sizes (which is polynomially in the input length; w.l.o.g. let \(p\) be an upper bound for this polynomial). This means that we argue on the duration of the \(i\)-th delay, which summarizes the time needed to find the \(i\)-th solution and to print it. To reach this delay, one uses two counters: one for the steps of \(\mathcal{A}\) (steps) and one for the solutions, initialized with value \(1\) (solindex). While simulating \(\mathcal{A}\), the solutions are inserted into a priority queue \(\mathcal{Q}\) instead of printing them. Eventually, the step counter reaches \(t(\kappa(x))\cdot p(|x|)\cdot\text{solindex}^{a+1}\). Then, the first element of \(\mathcal{Q}\) is extracted, output, and solindex is incremented by one. In view of this, \(\mathcal{A}\) computed solindex many solutions and prints the next one (or \(\mathcal{A}\) already halted). Combining these observations leads to calculating the \(i\)-th delay:  
\[O(t(\kappa(x))\cdot p(|x|)\cdot(i+1)^{a+1}-t(\kappa(x))\cdot p(| x|)\cdot i^{a+1}+s)\] \[=O(t(\kappa(x))\cdot p(|x|)\cdot q(i)+p(|x|))\] \[=O(t(\kappa(x))\cdot p(|x|)\cdot i^{a})\qquad(\text{as }q(i)\in O(i^{a}))\]  
Clearly, this is a delay of the required form \(t(\kappa(x))\cdot p(|x|)\cdot i^{a}\), and thus, \(E\in\text{IncFPT}_{a}\). Note that from the previous result, one can easily obtain the following corollary. **Corollary 2**: \(\text{CapIncFPT}_{1}=\text{DelayFPT}\) _and \(\text{CapIncFPT}=\text{IncFPT}\)._  
If one drops the restrictions 3. and 4. from Definition 3, then [PERSON] and [PERSON] unconditionally show a strict hierarchy for the cap-classes via utilizing the well-known time hierarchy theorem [42]. Of course, this result transfers also to the parameterized world, that is, to the same generalization of \(\text{CapIncFPT}_{a}\). Nonetheless, it is unknown whether a similar hierarchy can be unconditionally shown for these classes as well as for \(\text{IncFPT}_{a}\). **Open Problem 1**: _Can a similar hierarchy be unconditionally shown for these classes as well as for \(\text{IncFPT}_{a}\)?_  
This is a significant question of further research which is strengthened in the following section via connecting parameterized with classical enumeration complexity.