Editing Parameterized complexity (section)

==== ''W''[1] ====
{{Redirect|W(1)|the mathematical constant|omega constant}}
Examples of ''W''[1]-complete problems include
* deciding if a given graph contains a [[Clique (graph theory)|clique]] of size ''k''
* deciding if a given graph contains an [[Independent set (graph theory)|independent set]] of size ''k''
* deciding if a given nondeterministic single-tape Turing machine accepts within ''k'' steps ("short Turing machine acceptance" problem).  This also applies to nondeterministic [[Turing machine|Turing machines]] with ''f''(''k'') tapes and even ''f''(''k'') of ''f''(''k'')-dimensional tapes, but even with this extension, the restriction to ''f''(''k'') tape alphabet size is fixed-parameter tractable. Crucially, the branching of the Turing machine at each step is allowed to depend on ''n'', the size of the input. In this way, the Turing machine may explore ''n''<sup>O(''k'')</sup> computation paths.