  Let XNLP be the class of parameterized problems such that an instance of size
n with parameter k can be solved nondeterministically in time $f(k)n^{O(1)}$
and space $f(k)\log(n)$ (for some computable function f). We give a wide
variety of XNLP-complete problems, such as List Coloring and Precoloring
Extension with pathwidth as parameter, Scheduling of Jobs with Precedence
Constraints, with both number of machines and partial order width as parameter,
Bandwidth and variants of Weighted CNF-Satisfiability. In particular, this
implies that all these problems are W[t]-hard for all t. This also answers a
long standing question on the parameterized complexity of the Bandwidth
problem.
