Editing Parameterized complexity (section)

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

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 {{tmath|f(n)\log n}} nondeterministic choices are in&nbsp;''P''.

''W''[''P''] can be loosely thought of as the class of problems where we have a set {{mvar|S}} of {{mvar|n}} items, and we want to find a subset <math>T \subset S</math> of size {{mvar|k}} such that a certain property holds. We can encode a choice as a list of {{mvar|k}} integers, stored in binary. Since the highest any of these numbers can be is {{mvar|n}}, <math>\lceil\log_2 n\rceil</math> bits are needed for each number. Therefore <math>k \cdot \lceil\log_2 n\rceil </math> total bits are needed to encode a choice. Therefore we can select a subset <math>T\subset S</math> with <math>O(k\cdot \log n)</math> nondeterministic choices.