Non-deterministic constraint logic (NCL) is a simple model of computation
based on orientations of a constraint graph with edge weights and vertex
demands. NCL captures \PSPACE\xspace and has been a useful tool for proving
algorithmic hardness of many puzzles, games, and reconfiguration problems. In
particular, its usefulness stems from the fact that it remains \PSPACE-complete
even under severe restrictions of the weights (e.g., only edge-weights one and
two are needed) and the structure of the constraint graph (e.g., planar
\textsc{and/or}\xspace graphs of bounded bandwidth). While such restrictions on
the structure of constraint graphs do not seem to limit the expressiveness of
NCL, the building blocks of the constraint graphs cannot be limited without
losing expressiveness: We consider as parameters the number of weight-one edges
and the number of weight-two edges of a constraint graph, as well as the number
of \textsc{and}\xspace or \textsc{or}\xspace vertices of an
\textsc{and/or}\xspace constraint graph. We show that NCL is fixed-parameter
tractable (FPT) for any of these parameters. In particular, for NCL
parameterized by the number of weight-one edges or the number of
\textsc{and}\xspace vertices, we obtain a linear kernel. It follows that, in a
sense, NCL as introduced by Hearn and Demaine is defined in the most economical
way for the purpose of capturing \PSPACE.