3
$\begingroup$

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

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

If $\mathrm{FPT}=W[1]$, then we will not directly get an answer to $\mathrm{P}$ vs. $\mathrm{NP}$ (or at least, not that we know). The assumption that $\mathrm{FPT} \neq W[1]$ is a weaker claim than $\mathrm{P}\neq \mathrm{NP}$:

If $\mathrm{P} = \mathrm{NP}$, then there is polynomial time algorithm for the $W[1]$-complete problem $k$-Clique, so $\mathrm{FPT}= W[1]$. Taking the contrapositive, we get that $\mathrm{FPT}\neq W[1]$ implies $\mathrm{P}\neq \mathrm{NP}$.

Taking a step back, the entire concept of fixed parameter tractability implicitly assumes that there are problems for which we cannot obtain a polynomial time algorithm. By applying this concept to NP-complete problems, we make the assumption that we are unable to prove $\mathrm{P} = \mathrm{NP}$. While this argument does not rule out a proof of $\mathrm{FPT}=W[1]$ implies $\mathrm{P} = \mathrm{NP}$, it does not seem natural that a collapse of complexity classes designed to give more fine-grained results when $\mathrm{P}\neq \mathrm{NP}$ would imply $\mathrm{P} = \mathrm{NP}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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