I am trying to understand how this proof works

enter image description here

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

Please, I am weak.

  • 2
    $\begingroup$ It would be easier to discuss your question if you included enough context. For example, what is the paper you are screenshotting? $\endgroup$ Aug 22, 2022 at 9:31
  • $\begingroup$ This is not a research-level question. It should have been asked on cs.stackexchange.com rather than here. $\endgroup$ Aug 22, 2022 at 12:54
  • $\begingroup$ 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. $\endgroup$
    – Edee
    Aug 22, 2022 at 15:48
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 22, 2022 at 17:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Aug 22, 2022 at 19:42

1 Answer 1


(relatively) SHORT ANSWER:

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.


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()$.

Answering the question:

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()$.
  • $\begingroup$ I will read it word by word tonight after showering. Thank you first for this detailed explain, this afternoon, I got some simple explain from another book which is called "Parameterized Algorithm", I will share it with you later. I guess i am lacking of some knowledge on computational analysis, some terms are not familiar to me. And it makes it hard to understand the book "Parameterized Complexity Theory" on the first chapter. Thanks! $\endgroup$
    – Edee
    Aug 22, 2022 at 12:38
  • 7
    $\begingroup$ 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. $\endgroup$ Aug 22, 2022 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.