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?
Please, I am weak.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
(relatively) SHORT ANSWER:
If $f'()$ is not non-decreasing, either
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":
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: