  Markov proved that there exists an unrecognizable 4-manifold, that is, a
4-manifold for which the homeomorphism problem is undecidable. In this paper we
consider the question how close we can get to S^4 with an unrecognizable
manifold. One of our achievements is that we show a way to remove so-called
Markov's trick from the proof of existence of such a manifold. This trick
contributes to the complexity of the resulting manifold. We also show how to
decrease the deficiency (or the number of relations) in so-called Adian-Rabin
set which is another ingredient that contributes to the complexity of the
resulting manifold. Altogether, our approach allows to show that the connected
sum #_9(S^2 x S^2) is unrecognizable while the previous best result is the
unrecognizability of #_12(S^2 x S^2) due to Gordon.
