A method for adaptively performing video decoding includes: performing decoding complexity management based upon parameter representing processing capability related to the adaptive complexity video decoder, in order to determine whether to reduce decoding complexity of at least one component of a plurality of components within an adaptive complexity video decoder; and selectively reducing decoding complexity of a portion of components within the adaptive complexity video decoder. An associated adaptive complexity video decoder and an associated adaptive audio/video playback system are also provided. In particular, the adaptive complexity video decoder includes a plurality of components and a decoding complexity manager. When needed, the decoding complexity manager delays audio playback of audio information.