A parameterized problem is a subset $ L \subseteq \Sigma^* \times \mathbb N$ , where $ \Sigma$ is a finite alphabet. A parameterized problem is fixed parameter tractable, if it could be decided in time $ f(k)|x|^{O(1)}$ for some $ (x,k) \in L$ .

In terms of the problem definition, a Turing machine for $ L$ has access to the parameter. I noted that for some algorithms, for example the kernelization of vertex cover, the algorithm indeed must have access to it, whereas for others, for example clique paramterized by maximal degree, it does not need access to the parameter. The algorithm for the latter simply looks into the neighbourhood of every vertex if it contains a clique, hence it runs in time $ O(2^{\Delta} |x|)$ , where $ (x, \Delta) \in L$ .

Was this ever noted? And if so, is there some notion like FPT without access to the parameter, i.e., a problem $ L\subseteq \Sigma^*$ is in “FPT without access to the parameter”, if it runs in time $ f(k)|x|^{O(1)}$ for $ x \in L$ and some number $ k$ that depends on $ x$ (I avoid the term parameter, as it is not given as input)? Or would it not make sense to consider such a class?