Spectral degeneracies in Liouvillian generators of dissipative dynamics generically occur as exceptional points, where the corresponding non-Hermitian operator becomes non-diagonalizable. Steady states, i.e. zero-modes of Liouvillians, are considered a fundamental exception to this rule since a no-go theorem excludes non-diagonalizable degeneracies there. Here, we demonstrate that the crucial issue of diverging timescales in dissipative state preparation is largely tantamount to an asymptotic approach towards the forbidden scenario of an exceptional steady state in the thermodynamic limit. With case studies ranging from NP-complete satisfiability problems encoded in a quantum master equation to the dissipative preparation of a symmetry protected topological phase, we reveal the close relation between the computational complexity of the problem at hand, and the finite size scaling towards the exceptional steady state, exemplifying both exponential and polynomial scaling. Formally treating the weight $W$ of quantum jumps in the Lindblad master equation as a parameter, we show that exceptional steady states at the physical value $W=1$ may be understood as a critical point hallmarking the onset of dynamical instability.