While this is a useful result, I’d caution that lots of NP-complete problems are not like this, where the parameterized complexity is easy while the general complexity is hard, and assuming FPT != W[1], lots of NP-complete problems like the Clique problem are still basically impossible to solve in practice, so be wary of relying on parameterized complexity too much.
That also neatly solves the issue of whether P vs NP matters in practice: The answer is very likely yes, it does matter a lot in practice.
I’m a computational complexity noob so apologies if this question is elementary.
I thought if one could solve one NP-complete problem then one can solve all of them. But you say that the treewidth doesn’t help at all with the Clique problem. Is the parametrized complexity filtration by treewidth not preserved by equivalence between different NP-complete problems somehow?
To me, if this is true it exposes a much more serious flaw in computational complexity classes and does not resolve the issue of whether P vs NP matters in practice at all. My takeaway is that the definitions are too coarse, aren’t really capturing what’s going on. But likely I’m confused.
I thought if one could solve one NP-complete problem then one can solve all of them. But you say that the treewidth doesn’t help at all with the Clique problem. Is the parametrized complexity filtration by treewidth not preserved by equivalence between different NP-complete problems somehow?
All NP-complete problems should have parameters that makes the problem polynomial when bounded, trivially so by the ⇒ 3-SAT ⇒ Bayes Net translation, and using the treewidth bound.
This isn’t the case for the clique problem (finding max clique) because it’s not NP-complete (it’s not a decision problem), so we don’t necessarily expect its parameterized version to be polynomial tractable — in fact, it’s the k-clique problem (yes/no is there a clique larger than size k) that is NP-complete. (so by the above translation argument, there certainly exists some graphical quantity that when bounded makes the k-clique problem tractable, though I’m not aware of it, or whether it’s interesting)
To me, the interesting question is whether:
(1) translating a complexity-bounding parameter from one domain to another leads to quantities that are semantically intuitive and natural in the respective domain.
(2) and whether easy instances of the problems in the latter domain in-practice actually have low values of the translated parameter.
rambling: If not, then that implies we need to search for a new k for this new domain. Perhaps this can lead to a whole new way of doing complexity class characterization by finding natural k-s for all sorts of NP-complete problems (whose natural k-s don’t directly translate to one another), and applying these various “difficulty measures” to characterize your NP-complete problem at hand! (I wouldn’t be surprised if this is already widely studied.)
Looking at the 3-SAT example (Qi are the propositional variables, Ci the ORs, and X the AND with Ai serving as intermediate ANDs):
re: (1), at first glance the treewidth of 3-SAT (clearly dependent on the structure of the Qi - Cj interaction) doesn’t seem super insightful or intuitive, though we may count the statement “a 3-SAT problem gets exponentially harder as you increase the formula-treewidth” as progress.
… but even that wouldn’t be an if and only if characterization of 3-SAT difficulty, because re: (2) there exist easy-in-practice 3-SAT problems that don’t necessarily have bounded treewidth (i haven’t read the link).
I would be interested in a similar analysis for more NP-complete problems known to have natural parameterized complexity characterization.
While this is a useful result, I’d caution that lots of NP-complete problems are not like this, where the parameterized complexity is easy while the general complexity is hard, and assuming FPT != W[1], lots of NP-complete problems like the Clique problem are still basically impossible to solve in practice, so be wary of relying on parameterized complexity too much.
That also neatly solves the issue of whether P vs NP matters in practice: The answer is very likely yes, it does matter a lot in practice.
Whats FPT!=W[1] ?
I’m a computational complexity noob so apologies if this question is elementary.
I thought if one could solve one NP-complete problem then one can solve all of them. But you say that the treewidth doesn’t help at all with the Clique problem. Is the parametrized complexity filtration by treewidth not preserved by equivalence between different NP-complete problems somehow?
To me, if this is true it exposes a much more serious flaw in computational complexity classes and does not resolve the issue of whether P vs NP matters in practice at all. My takeaway is that the definitions are too coarse, aren’t really capturing what’s going on. But likely I’m confused.
All NP-complete problems should have parameters that makes the problem polynomial when bounded, trivially so by the ⇒ 3-SAT ⇒ Bayes Net translation, and using the treewidth bound.
This isn’t the case for the clique problem (finding max clique) because it’s not NP-complete (it’s not a decision problem), so we don’t necessarily expect its parameterized version to be polynomial tractable — in fact, it’s the k-clique problem (yes/no is there a clique larger than size k) that is NP-complete. (so by the above translation argument, there certainly exists some graphical quantity that when bounded makes the k-clique problem tractable, though I’m not aware of it, or whether it’s interesting)
To me, the interesting question is whether:
(1) translating a complexity-bounding parameter from one domain to another leads to quantities that are semantically intuitive and natural in the respective domain.
(2) and whether easy instances of the problems in the latter domain in-practice actually have low values of the translated parameter.
rambling: If not, then that implies we need to search for a new k for this new domain. Perhaps this can lead to a whole new way of doing complexity class characterization by finding natural k-s for all sorts of NP-complete problems (whose natural k-s don’t directly translate to one another), and applying these various “difficulty measures” to characterize your NP-complete problem at hand! (I wouldn’t be surprised if this is already widely studied.)
Looking at the 3-SAT example (Qi are the propositional variables, Ci the ORs, and X the AND with Ai serving as intermediate ANDs):
re: (1), at first glance the treewidth of 3-SAT (clearly dependent on the structure of the Qi - Cj interaction) doesn’t seem super insightful or intuitive, though we may count the statement “a 3-SAT problem gets exponentially harder as you increase the formula-treewidth” as progress.
… but even that wouldn’t be an if and only if characterization of 3-SAT difficulty, because re: (2) there exist easy-in-practice 3-SAT problems that don’t necessarily have bounded treewidth (i haven’t read the link).
I would be interested in a similar analysis for more NP-complete problems known to have natural parameterized complexity characterization.
Yeah, I probably messed up here quite a bit, sorry.