Name
Abstract | ||
|---|---|---|
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 alpha, where alpha 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] subset of or equal to W[2] subset of or equal to ... 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. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1002/malq.19970430204 | MATHEMATICAL LOGIC QUARTERLY |
Keywords | Field | DocType |
turing machine,computational complexity,parameterized computational complexity | 2-EXPTIME,PH,Discrete mathematics,DTIME,Computational problem,Parameterized complexity,Structural complexity theory,Combinatorics,Nondeterministic algorithm,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
43 | 2 | 0942-5616 |
Citations | PageRank | References |
12 | 1.33 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marco Cesati | 1 | 185 | 12.53 |
| Miriam di Ianni | 2 | 144 | 17.27 |