For instance, Subset Sum is classified :

    W[1]-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.

  • $\begingroup$ 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. $\endgroup$ – rus9384 Oct 5 '17 at 4:39
  • $\begingroup$ Algorithms are not members of complexity classes. $\endgroup$ – Raphael Oct 5 '17 at 4:54
  • 2
    $\begingroup$ 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! $\endgroup$ – Raphael Oct 5 '17 at 4:54
  • $\begingroup$ Sure, I don't know what I was thinking when writing the question, thanks for the heads up! $\endgroup$ – Jesus Salas Oct 5 '17 at 5:08
  • $\begingroup$ 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. $\endgroup$ – 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}[2]$-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.

So a different parameter choice gives you different parameterizations, and hence (possibly) different complexity. Another way to think of it is that the parameterizations tell you which part of the input is the bit that makes the problem hard - so Dominating Set is hard when the graph has very large treewidth, but the size of the solution doesn't really play into it (i.e. when we "control" it by making it the parameter, the problem doesn't get easier, in contrast to say, Vertex Cover).

This approach allows problems to be examined from many angles via different parameterizations, to get a better quantified understanding of the sources of complexity for that problem.

The classical approach is more-or-less like taking a trivial parameterization for every problem (e.g. we just set the parameter to 1, regardless of the input) - this statement is a bit wonky, but a not-to-bad approximation to develop some intuition from.

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

| cite | improve this answer | |
  • $\begingroup$ thank you so much for your response, I just started reading about complexity parametrization and raised some questions on my head, I'm going to complement the question to name the parameter, if that helps to provide a more accurate answer $\endgroup$ – Jesus Salas Oct 5 '17 at 5:39
  • $\begingroup$ Reading again your answer, the classical approach, as you suggest looks really trivial, as an engineer I feel like that complexity parametrization makes more sense and helps understand much better what are the limits and cost implications of a problem $\endgroup$ – Jesus Salas Oct 5 '17 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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