Parameterized complexity: Difference between revisions

Revision as of 19:05, 19 December 2009

Revision as of 08:54, 13 January 2010

Line 50:

It is known that FPT is contained in W[P], and the inclusion is believed to be strict. However, resolving this issue would imply a solution to the [[P versus NP]] problem.

Other connections to unparameterised computational complexity are that FPT equals W[P] if and only if [[Circuit satisfiability]] can be decided in time $<math>\exp(o(n))m^{O(1)}$</math>, or if and only if there is a computable, nondecreasing, unbounded function f such that all languages recognised by a nondeterministic polynomial-time Turing machine using f(n)log n nondeterministic steps are in P.

==References==