Next-generation optical communication systems will continue to push the ( bandwidth · distance) product towards its physical limit. To address this enormous demand, the usage of digital signal processing together with advanced modulation formats and coherent detection has been proposed to enable data-rates as high as 400 Gb/s per channel over distances in the order of 1000 km. These technological breakthroughs have been made possible by full compensation of linear fiber impairments using digital equalization algorithms. While linear equalization techniques have already matured over the last decade, the next logical focus is to explore solutions enabling the mitigation of the Kerr effect induced nonlinear channel impairments. One of the most promising methods to compensate for fiber nonlinearities is digital back-propagation (DBP), which has recently been acknowledged as a universal compensator for fiber propagation impairments, albeit with high computational requirements. In this paper, we discuss two proposals to reduce the hardware complexity required by DBP. The first confirms and extends published results for non-dispersion managed link, while the second introduces a novel method applicable to dispersion managed links, showing complexity reductions in the order of 50% and up to 85%, respectively. The proposed techniques are validated by comparing results obtained through post-processing of simulated and experimental data, employing single channel and WDM configurations, with advanced modulation formats, such as quadrature phase shift keying (QPSK) and 16-ary quadrature amplitude modulation (16-QAM). The considered net symbol rate for all cases is 25 GSymbol/s. Our post-processing results show that we can significantly reduce the hardware complexity without affecting the system performance. Finally, a detailed analysis of the obtained reduction is presented for the case of dispersion managed link in terms of number of required complex multiplications per transmitted bit.