ANN applications often have a combinatorial bottleneck, where locality is violated, and you have to compare everything to everything. It feels similar to P-NP: if you solve it once you solve them all. I suspect it is unsolvable tho, or we would have evolved a solver in our heads!
Yet all we have is heuristics. The good news is that computers are more efficient with heuristics, as they can remember more, and without decay. So in practice, a combo of ANN “intuition”, greedy sampling, and perfect Von Neumann memory can totally do the trick.