  The concept of space-bounded computability has become significantly important
in handling vast data sets on memory-limited computing devices. To replenish
the existing short list of NL-complete problems whose instance sizes are
dictated by log-space size parameters, we propose new additions obtained
directly from natural parameterizations of three typical NP-complete problems
-- the vertex cover problem, the exact cover by 3-sets problem, and the
3-dimensional matching problem. With appropriate restrictions imposed on their
instances, the proposed decision problems parameterized by appropriate size
parameters are proven to be equivalent in computational complexity to either
the parameterized $3$-bounded 2CNF Boolean formula satisfiability problem or
the parameterized degree-$3$ directed $s$-$t$ connectivity problem by ``short''
logarithmic-space reductions. Under the assumption of the linear space
hypothesis, furthermore, none of the proposed problems can be solved in
polynomial time if the memory usage is limited to sub-linear space.
