# Need more explaination on this 'generality'

I am trying to understand how this proof works

I don't understand, why this f' is nondecreasing? What kind of generality makes us come up with such kind of assumption?

• It would be easier to discuss your question if you included enough context. For example, what is the paper you are screenshotting? Aug 22, 2022 at 9:31
• This is not a research-level question. It should have been asked on cs.stackexchange.com rather than here. Aug 22, 2022 at 12:54
• I already asked at CS stack, they told me to relocate here. @EmilJeřábek , I know the question seems stupid, but I also don't think it could be easily answered in the right way by some prof. or A/prof.
– Edee
Aug 22, 2022 at 15:48
• If you are unfamiliar with the “without loss of generality” idiom, see en.wikipedia.org/wiki/Without_loss_of_generality . I am not an expert in computational analysis, but generally speaking, you become familiar with terms and idioms in a particular field by reading more and more papers and books on the topic, it requires time and patience. It’s not that you could just read a glossary and suddenly understand everything. Aug 22, 2022 at 17:30
• Can you provide any link to where you received that feedback on CS.SE? It doesn't appear that you have asked any questions from your account on CS.SE.
– D.W.
Aug 22, 2022 at 19:42

If $$f'()$$ is not non-decreasing, either

1. one can define a strictly increasing function $$g'()$$ such that $$f'(g'(k))$$ is non-decreasing, and apply the result to the function $$f'(g'())$$; or
2. there is a decreasing function $$F'(k)$$ such that $$f'(k)\leq F'(k) \forall k$$, and $$(Pb,k)\in FPT$$ implies that $$Pb\in P$$.

Assuming that $$f'()$$ is non decreasing is equivalent to 1) assuming that $$Pb$$ cannot be proven to be in $$P$$ so easily (because then it would not make sense to analyze it for FPT) and 2) avoiding defining the function $$g'()$$ and a variant $$Pb'$$ of $$Pb$$ such the function $$f''()$$ in the analysis of its complexity is non decreasing. It can be assumed "without loss of generality" and makes the definitions, result statements and proofs considerably shorter and easier to read.

LONGER EXPLANATION:

A short introduction:

The class of "Fixed Parameter Tractable" (FPT)" problems was introduced in order to refine the class of "Non-deterministic Polynomial time" (NP) problems into smaller classes if difficulty, each class being defined by a parameter $$k$$, which you can think about as a "measure of difficulty":

• when $$k$$ is unbounded and can get very large, the worst case is bounded only by the size of the instance and the only analysis standing is that of NP problems; whereas
• when the value of the parameter $$k$$ is bounded, and in particular when it is fixed, the problem is said "Fixed Parameter Tractable" if there exists an algorithm which running time is polynomial in the size of the input (e.g. an algorithm running in time within $$O(n^{k})$$ would be polynomial for fixed or bounded values of $$k$$ but not in general if $$k$$ can depend on $$n$$).

Formally, the pair $$(*Pb,k)$$ formed by a problem $$Pb$$ and a parameter $$k$$ is within $$FPT$$ if there exists an algorithm solving $$Pb$$ which runs in polynomial time in the size $$|x|$$ of the input $$x$$ for any fixed value of $$k$$. That includes running times within $$O(f(k)\times p(|x|))$$ for any polynomial $$p()$$ and any function $$f()$$.

The notion of FPT is useless if $$f()$$ is non decreasing:
• as a warming up example, consider the case where $$f(k)$$ would be decreasing: if a pair $$(Pb,k)\in FPT$$ with such a function $$f(k)$$, then $$Pb$$ can be solved in polynomial time for any value of $$k$$, so there is no need to consider the parameter $$k$$ to refine its analysis beyond $$P$$.
• more generally, consider the case where $$f(k)$$ is locally decreasing on some intervals, but that there is a strictly increasing integer function $$g()$$ such that $$f(g(k))$$ is non decreasing: while being able to solve $$Pb$$ faster for some particular values of $$k$$ might be interesting in practice, in theory we are interested in solving it faster all the time (now knowing what future instances will look like), so we focus on the parts where $$f()$$ is non decreasing and, "without loss of generality", just assume that $$f()$$ is non decreasing to avoid having to introduce the function $$g()$$.
• You are making it way too complicated, and I’m sure this not what the authors meant. Simply, if $\mathbb A'$ decides $(Q',\kappa')$ in time (at most) $f'(k')\cdot p'(|x'|)$, it also decides it in time $f''(k')\cdot p'(|x'|)$, where $f''(k')=\max\{f'(n):n\le k'\}$ is nondecreasing. Thus, without loss of generality, we may assume $f'=f''$, i.e., that $f'$ is already nondecreasing. Aug 22, 2022 at 12:50