Bounded fixed-parameter tractability and reducibility

Annals of Pure and Applied Logic 148 (1):1-19 (2007)
  Copy   BIBTEX

Abstract

We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family . For every family of functions, this yields a notion of -fixed-parameter tractability. If is the class of all polynomially bounded functions, then -fixed-parameter tractability coincides with polynomial time decidability and if is the class of all computable functions, -fixed-parameter tractability coincides with the standard notion of fixed-parameter tractability. There are interesting choices of between these two extremes, for example the class of all singly exponential functions. In this article, we study the general theory of -fixed-parameter tractability. We introduce a generic notion of reduction and two classes -W[P] and -XP, which may be viewed as analogues of NP and EXPTIME, respectively, in the world of -fixed-parameter tractability

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,931

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On the complexity of Gödel's proof predicate.Yijia Chen & Jörg Flum - 2010 - Journal of Symbolic Logic 75 (1):239-254.
Bounded enumeration reducibility and its degree structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
Intrinsic Reducibilities.Timothy H. McNicholl - 2000 - Mathematical Logic Quarterly 46 (3):393-407.
Invitation to fixed-parameter algorithms.Rolf Niedermeier - 2006 - New York: Oxford University Press.
On fixed-point logic with counting.Jörg Flum & Martin Grohe - 2000 - Journal of Symbolic Logic 65 (2):777-787.
On existence of complete sets for bounded reducibilities.Valeriy Bulitko & Vadim Bulitko - 2003 - Mathematical Logic Quarterly 49 (6):567-575.
A New Reducibility between Turing‐ and wtt‐Reducibility.Sui Yuefei - 1994 - Mathematical Logic Quarterly 40 (1):106-110.
Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
Quasi‐completeness and functions without fixed‐points.Ilnur I. Batyrshin - 2006 - Mathematical Logic Quarterly 52 (6):595-601.

Analytics

Added to PP
2013-12-30

Downloads
51 (#320,237)

6 months
41 (#98,048)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations