Decelle et al.'s computational impossibility conjecture below the Kesten–Stigum threshold

Let $(X,G)$ follow the same stochastic block model as in the achievability conjecture, with

$$\operatorname{SNR}=\frac{(a-b)^2}{k(a+(k-1)b)}.$$

Decelle et al.'s computational impossibility conjecture. Irrespective of $k$, if $\operatorname{SNR}<1$, it is impossible to detect communities in polynomial time. This is the computational counterpart to the Kesten–Stigum achievability statement. The source presents it among further conjectures concerning impossibility statements; no resolution is given in the supplied text.