The problem of sequence detection in frequency-nonselective/time-selective fading channels, when channel state information (CSI) is not available at the transmitter and receiver, is considered in this paper. The traditional belief is that exact maximum-likelihood sequence detection (MLSD) of an uncoded sequence over this channel has exponential complexity in the channel coherence time. Thus, for slowly varying channels, i.e., channels having coherence time on the order of the sequence length, the complexity appears to be exponential in the sequence length. In the first part of this work, it is shown that exact MLSD can be computed with only polynomial worst case complexity in the sequence length regardless of the operating signal-to-noise ratio (SNR) for equal-energy signal constellations. By establishing a relationship between the aforementioned complexity and the rank of the correlation matrix of the fading process, an understanding of how complexity of the optimal MLSD receiver varies as the channel dynamics change is provided. In the second part of this paper, the problem of decoding turbo-like codes in frequency-nonselective/time-selective fading channels without receiver CSI is examined. Using arguments similar to the ones used for the MLSD case, it is shown that the exact symbol-by-symbol soft-decision metrics (SbSSDMs) implied by the min-sum algorithm can be evaluated with polynomial worst case complexity in the sequence length regardless of SNR for equal-energy signal constellations. Finally, by simplifying some key steps in the polynomial-complexity algorithm, a family of fast, approximate algorithms is derived, which yield near-optimal performance