  We study the Parallel Task Scheduling problem $Pm|size_j|C_{\max}$ with a
constant number of machines. This problem is known to be strongly NP-complete
for each $m \geq 5$, while it is solvable in pseudo-polynomial time for each $m
\leq 3$. We give a positive answer to the long-standing open question whether
this problem is strongly $NP$-complete for $m=4$. As a second result, we
improve the lower bound of $\frac{12}{11}$ for approximating pseudo-polynomial
Strip Packing to $\frac{5}{4}$. Since the best known approximation algorithm
for this problem has a ratio of $\frac{4}{3} + \varepsilon$, this result
narrows the gap between approximation ratio and inapproximability result by a
significant step. Both results are proven by a reduction from the strongly
$NP$-complete problem 3-Partition.
