# In the context of parametrized complexity

For instance, Subset Sum is classified :

    W-hard, in W[P] (parameter:k, subset cardinality)


by the Compendium of Parameterized Problems, how the parameter could impact the membership of the problem on a specific class?

Looks like Parametrized Complexity is trying to provide a better problem classification for NP-hard problems.

• Paramatrized complexity shows relation between parameters and complexity. For example, SAT, asking whether there is a partial assignment (that satisfies all clauses) of length $k$ is solvable in polynomial time, when $k$ is fixed. If you unfix it, the formula $O(n^k)$ is no more polynomial. – rus9384 Oct 5 '17 at 4:39
• Algorithms are not members of complexity classes. – Raphael Oct 5 '17 at 4:54
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Oct 5 '17 at 4:54
• Sure, I don't know what I was thinking when writing the question, thanks for the heads up! – Jesus Salas Oct 5 '17 at 5:08
• Also, the proposition that it tries to give better classification for NPC problems is not 100% correct. We can define another parametrized complexity classes. QBF with $O(\log n)$ amount of $\forall$ quantifiers is in NP, as an example. – rus9384 Oct 5 '17 at 5:13

Firstly, there is an important part of the quoted statement you are missing - the parameterization. It can only be classified with respect to some parameterization. For example, Dominating Set is $\mathrm{W}$-complete when parameterized by $k$, the size of the dominating set, but it is in $\mathrm{FPT}$ when parameterized by the treewidth of the input graph.
To address your final statement, yes, that is one of the inspirations for the development of Parameterized Complexity - the observation that some $\mathrm{NP}$-complete problems had really good algorithms, but others were apparently completely intractable in practice. The theory was at least partially developed to provide a formalised way of approaching this weakness in classical complexity (the inability to certain classes of problems).