  In this paper the recoverable robust shortest path problem is investigated.
Discrete budgeted interval uncertainty representation is used to model
uncertain second-stage arc costs. The known complexity results for this problem
are strengthened. It is shown that it is Sigma_3^p-hard for the arc exclusion
and the arc symmetric difference neighborhoods. Furthermore, it is also proven
that the inner adversarial problem for these neighborhoods is Pi_2^p-hard.
