Thumbnail
Access Restriction
Open

Author Abrahamson, Karl A. ♦ Downey, Rodney G. ♦ Fellows, Michael R.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract We describe new results in parameterized 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 parameterized complexity of analogues of P SP ACE 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 of the DTIME(2^o(n)) and NP.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2010-01-01