### M. Cesati, M. Di Ianni, ``Computation Models for
Parameterized Complexity'', Mathematical Logic Quarterly, 43
(1997), 179-202, Johann Ambrosius Barth

A parameterized computational problem is a set of pairs
(x,k), where k is a distinguished item called ``parameter''.
FPT is the class of fixed-parameter
tractable problems: for any fixed value k, they are solvable in
time bounded by a polynomial of degree c, where c is a constant
not dependent on the parameter. In order to deal with
parameterized intractability, Downey and Fellows have
introduced a hierarchy of classes W[1] \subseteq W[2]
\subseteq ... containing likely intractable parameterized
problems, and they have shown that such classes have many
natural, complete languages. In this paper we analyze several
variations of the halting problem for nondeterministic Turing
machines with parameterized time, and we show that its
parameterized complexity strongly depends on some resources
like the number of tapes, heads and internal states, and on the
size of the alphabet. Notice that classical polynomial-time
complexity fails in distinguishing such features. As
byproducts, we show that parameterized complexity is a useful
tool for the study of the intrinsic power of some computational
models, and we underline the different ``computational powers''
of some levels of the parameterized hierarchy.

Back to the Marco
Cesati's research page.