  We present the first results on the parameterized complexity of
reconfiguration problems, where a reconfiguration version of an optimization
problem $Q$ takes as input two feasible solutions $S$ and $T$ and determines if
there is a sequence of {\em reconfiguration steps} that can be applied to
transform $S$ into $T$ such that each step results in a feasible solution to
$Q$. For most of the results in this paper, $S$ and $T$ are subsets of vertices
of a given graph and a reconfiguration step adds or deletes a vertex. Our study
is motivated by recent results establishing that for most NP-hard problems, the
classical complexity of reconfiguration is PSPACE-complete. We address the
question for several important graph properties under two natural
parameterizations: $k$, the size of the solutions, and $\ell$, the length of
the sequence of steps. Our first general result is an algorithmic paradigm, the
{\em reconfiguration kernel}, used to obtain fixed-parameter algorithms for the
reconfiguration versions of {\sc Vertex Cover} and, more generally, {\sc
Bounded Hitting Set} and {\sc Feedback Vertex Set}, all parameterized by $k$.
In contrast, we show that reconfiguring {\sc Unbounded Hitting Set} is
$W[2]$-hard when parameterized by $k+\ell$. We also demonstrate the
$W[1]$-hardness of the reconfiguration versions of a large class of
maximization problems parameterized by $k+\ell$, and of their corresponding
deletion problems parameterized by $\ell$; in doing so, we show that there
exist problems in FPT when parameterized by $k$, but whose reconfiguration
versions are $W[1]$-hard when parameterized by $k+\ell$.
