In this work, we clarify, extend and solve a long-standing open
problem concerning the computational complexity for packet scheduling
algorithms to achieve tight end-to-end delay bounds.  We first focus
on the difference between the time a packet finishes service in a
scheduling algorithm and its virtual finish time under a GPS (General
Processor Sharing) scheduler, called {\it GPS-relative delay}.  We
prove that, under a slightly restrictive but reasonable computational
model, the lower bound computational complexity of any scheduling
algorithm that guarantees $O(1)$ GPS-relative delay bound is
$\Omega(\log n)$.  We also discover that, surprisingly, the complexity
lower bound remains the same even if the delay bound is relaxed to
$O(n^a)$ for $0<a<1$.  This implies that the delay-complexity tradeoff
curve is flat in the ``interval'' $[O(1)$, $O(n))$.  We later
conditionally extend both complexity results (for $O(1)$ or $O(n^a)$
delay) to a much stronger computational model, the linear decision
tree.  Finally, we show that the same complexity lower bounds are
conditionally applicable to guaranteeing tight end-to-end delay
bounds, if the delay bounds are provided through the Latency Rate (LR)
framework.