Content deleted Content added
→XP: Explaining XP. Still could use examples etc. Tags: Mobile edit Mobile web edit |
→W hierarchy: Elaborating on single-tape/multi-tape, what aspects are bounded or not |
||
Line 44:
* 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 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.
==== ''W''[2] ====
Examples of ''W''[2]-complete problems include
* deciding if a given graph contains a [[dominating set]] of size ''k''
* deciding if a given nondeterministic [[Turing machine equivalents#Multi-tape Turing machines|multi-tape Turing machine]] accepts within ''k'' steps ("short multi-tape Turing machine acceptance" problem). Crucially, the branching is allowed to depend on ''n'' (like the W[1] variant), as is the number of tapes. An alternate ''W''[2]-complete formulation allows only single-tape Turing machines, but the alphabet size may depend on ''n''.
==== ''W''[''t''] ====
| |||