HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Relationship between complexity classes W[1] and NP?

Submitted by: @import:stackexchange-cs··
0
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$.

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.

Context

StackExchange Computer Science Q#142516, answer score: 2

Revisions (0)

No revisions yet.