Parameterized complexity: Difference between revisions

Revision as of 15:10, 20 April 2022

Revision as of 09:58, 7 September 2022

Line 67:

==== ''W''[''P''] ====

''W''[''P''] is the class of problems that can be decided by a nondeterministic <math>h(k) \cdot {|x|}^{O(1)}</math>-time Turing machine that makes at most Tu<math>O(f(k)\cdot \log n)</math> nondeterministic choices in the computation on <math>(x,k)</math> (a ''k''-restricted Turing machine). {{harvtxt|Flum|Grohe|2006}}

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.