6 found
Order:
  1.  4
    Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory.Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip & Frances A. Rosamond - 2022 - Artificial Intelligence 303:103644.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  13
    Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues.Karl A. Abrahamson, Rodney G. Downey & Michael R. Fellows - 1995 - Annals of Pure and Applied Logic 73 (3):235-276.
    We describe new results in parametrized complexity theory. In particular, we prove a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in terms (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  27
    Index Sets and Parametric Reductions.Rod G. Downey & Michael R. Fellows - 2001 - Archive for Mathematical Logic 40 (5):329-348.
    We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W e ≤ q u A} for q∈ {m, T} are Σ4 0 complete. We also show hat FPT(≤ q n ), that is {e : W e computable and ≡ q n ?}, is Σ4 (...)
    No categories
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  4.  32
    On the Parameterized Complexity of Short Computation and Factorization.Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows - 1997 - Archive for Mathematical Logic 36 (4-5):321-337.
    . A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  5
    Sparse Parameterized Problems.Marco Cesati & Michael R. Fellows - 1996 - Annals of Pure and Applied Logic 82 (1):1-15.
    Sparse languages play an important role in classical structural complexity theory. In this paper we introduce a natural definition of sparse problems for parameterized complexity theory. We prove an analog of Mahaney's theorem: there is no sparse parameterized problem which is hard for the tth level of the W hierarchy, unless the W hierarchy itself collapses up to level t. The main result is proved for the most general form of parametric many:1 reducibility, where the parameter functions are not assumed (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  6.  12
    Advice Classes of Parameterized Tractability.Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows - 1997 - Annals of Pure and Applied Logic 84 (1):119-138.
    Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation