  Recently, considerable focus has been given to the problem of determining the
boundary between tractable and intractable planning problems. In this paper, we
study the complexity of planning in the class C_n of planning problems,
characterized by unary operators and directed path causal graphs. Although this
is one of the simplest forms of causal graphs a planning problem can have, we
show that planning is intractable for C_n (unless P = NP), even if the domains
of state variables have bounded size. In particular, we show that plan
existence for C_n^k is NP-hard for k>=5 by reduction from CNFSAT. Here, k
denotes the upper bound on the size of the state variable domains. Our result
reduces the complexity gap for the class C_n^k to cases k=3 and k=4 only, since
C_n^2 is known to be tractable.
