This note addresses the discrete version of the well-known time-cost t
radeoff problem for project networks, which has been studied previousl
y in the standard project management literature as well as in the rela
ted literature on Decision-CPM, All the algorithms proposed thus far f
or the solution of the general problem exhibit exponential worst-case
complexity, with the notable exception of the pseudo-polynomial dynami
c program due to Hindelang and Muth. We first demonstrate that this al
gorithm is flawed, and that when we correct it. it no longer remains p
seudo-polynomial. Continuing on in the main result of the note, we sho
w that this is not at all surprising, since the problem is strongly NP
-hard. Finally, we discuss the complexities of various network structu
res and validate an old conjecture that certain structures are necessa
rily more difficult to solve.