Content deleted Content added
→W[1]: improve the previous edit |
m →W[1]: clarify |
||
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.
==== ''W''[2] ====
| |||