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 a 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[I] ⊆ 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.

Cesati, M., & Di Ianni, M. (1997). Computation models for parameterized complexity. MATHEMATICAL LOGIC QUARTERLY, 43(2), 179-202 [10.1002/malq.19970430204].

Computation models for parameterized complexity

Cesati M.
;
Di Ianni M.
1997

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 α, where a 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[I] ⊆ 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.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore ING-INF/05
English
Computational complexity
Parameterized computational complexity
Turing machine
https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19970430204
Cesati, M., & Di Ianni, M. (1997). Computation models for parameterized complexity. MATHEMATICAL LOGIC QUARTERLY, 43(2), 179-202 [10.1002/malq.19970430204].
Cesati, M; Di Ianni, M
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
malq.19970430204.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 1.54 MB
Formato Adobe PDF
1.54 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/260205
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 14
social impact