Premium
Computation Models for Parameterized Complexity
Author(s) -
Cesati Marco,
Dilanni Miriam
Publication year - 1997
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19970430204
Subject(s) - parameterized complexity , polynomial hierarchy , mathematics , nondeterministic algorithm , complexity class , computational complexity theory , time complexity , time hierarchy theorem , dtime , bounded function , hierarchy , discrete mathematics , ph , turing machine , np , set (abstract data type) , combinatorics , computation , computer science , algorithm , quantum complexity theory , universal turing machine , mathematical analysis , physics , quantum mechanics , economics , quantum information , market economy , quantum , programming language
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 of k , they are solvable in time bounded by a polynomial of degree α, where α 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[l] ⊆ W[2] ⊆ ⃛ 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, head 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.