Parameterized complexity: Difference between revisions

Revision as of 14:14, 23 May 2019

Revision as of 10:15, 13 June 2019

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