Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state ρ, while only requiring measurements on logarithmically many copies of ρ in the size of P. In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized" for low-Frobenius norm observables, i.e., solved in randomized poly-time with standard sampling assumptions. Finally, we show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class.