patternMinor
Relationship between complexity classes W[1] and NP?
Viewed 0 times
betweenclassesandcomplexityrelationship
Problem
I am trying to understand the connection between The W-hierarchy as presented in chapter 13 of this book by Cygan et al. and the notion of the NP problems.
Is the existence of an FPT algorithm for a problem in W[1] suggests that P=NP? Why?
For example, assuming I have an FPT algorithm for the k-Clique problem. Can I prove the P=NP? The algorithm run time will still be exponential. Only now, it will depend on $k$.
Is the existence of an FPT algorithm for a problem in W[1] suggests that P=NP? Why?
For example, assuming I have an FPT algorithm for the k-Clique problem. Can I prove the P=NP? The algorithm run time will still be exponential. Only now, it will depend on $k$.
Solution
Because $k$-CLIQUE is W[1]-hard, your result would imply that FPT = W[1], which by the result of Downey and Fellows [1] implies that the Exponential Time Hypothesis (ETH) is false, i.e., that 3-SAT can be solved in $2^{o(n)}$ time. But ETH is stronger than P not equal to NP, so its falsification doesn't settle P = NP (but of course, if true, ETH would imply that P is not equal to NP).
As far as I know, FPT = W[1] is not known to imply anything else regarding the W-hierarchy.
[1] Downey, Rodney G., and Michael Fellows. Parameterized complexity. Springer Science & Business Media, 2012.
As far as I know, FPT = W[1] is not known to imply anything else regarding the W-hierarchy.
[1] Downey, Rodney G., and Michael Fellows. Parameterized complexity. Springer Science & Business Media, 2012.
Context
StackExchange Computer Science Q#142516, answer score: 2
Revisions (0)
No revisions yet.