{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:21:50Z","timestamp":1737091310305,"version":"3.33.0"},"reference-count":9,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3603,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1997,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A parameterized computational problem is a set of pairs (<jats:italic>x<\/jats:italic>,<jats:italic>k<\/jats:italic>), where<jats:italic>k<\/jats:italic>is a distinguished item called \u201cparameter\u201d. FPT is the class of fixed\u2010parameter tractable problems: for any fixed value of<jats:italic>k<\/jats:italic>, they are solvable in time bounded by a polynomial of degree \u03b1, where \u03b1 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] \u2286 W[2] \u2286 \u20db 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\u2010time 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 \u201ccomputational powers\u201d of some levels of the parameterized hierarchy.<\/jats:p>","DOI":"10.1002\/malq.19970430204","type":"journal-article","created":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T01:56:20Z","timestamp":1180490180000},"page":"179-202","source":"Crossref","is-referenced-by-count":15,"title":["Computation Models for Parameterized Complexity"],"prefix":"10.1002","volume":"43","author":[{"given":"Marco","family":"Cesati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miriam","family":"Dilanni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"Cai L. J.Chen R. G.Downey andM. R.Fellows On the parameterized complexity of short computation and factorization. To appear in the Archive for Mathematical Logic."},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"Downey R. G. andM. R.Fellows Fixed\u2010parameter intractability (extended abstract). In: Proceedings of the 7th IEEE Conference on Structure in Complexity Theory Boston June1992 pp.36\u201349.","DOI":"10.1109\/SCT.1992.215379"},{"key":"e_1_2_1_4_2","first-page":"161","article-title":"Fixed\u2010parameter tractability and completeness","volume":"87","author":"Downey R. G.","year":"1992","journal-title":"Congressus Numerantium"},{"volume-title":"Feasible Mathematics II","year":"1994","author":"Downey R. G.","key":"e_1_2_1_5_2"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_1_8_2"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90041-0"},{"volume-title":"Elements of the Theory of Computation","year":"1981","author":"Lewis H. R.","key":"e_1_2_1_10_2"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19970430204","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19970430204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T19:19:19Z","timestamp":1737055159000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19970430204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["10.1002\/malq.19970430204"],"URL":"https:\/\/doi.org\/10.1002\/malq.19970430204","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}