The immediate problem with locating our space in the string theory landscape today, is that even if you pick just one definite background geometry (definite shape for the extra dimensions, etc), you will not be able to calculate particle masses and other measurable quantities. The calculations are too difficult and there are too many unknown aspects of the theory.
At this time, when people look for string "vacua" that might be the real world, they first filter the possibilities through qualitative constraints. An elementary example of such a constraint, is that we observe three dimensions of space. But what the professional physicists actually want, is something that will give the symmetry groups and particle multiplets that have been observed in high-energy physics.
The governing paradigm here is "grand unification", the identification of a single symmetry group which has the symmetries of the known forces as subgroups. This was already the mainstream of particle physics before the modern wave of string theory (beginning in 1984). So realistic string-theory model-building consists of identifying string vacua in which the strings become matter fields interacting according to unified gauge forces like SU(5) or SO(10), that can then be broken to the standard model forces by Higgs effects.
There would be thousands of string vacua known which satisfy that description, I think. But to really test them, either you need some completely new effect, like a new particle state with nonstandard charges, or you need to be able to calculate e.g. the exact masses of the particles in these vacua which are analogous to the electron, the top quark, and so on - so as to determine whether they are the electron, top quark, etc of the real world.
And that is simply not achievable at this point. People get excited e.g. if they have a model in which one of the "quarks" is much heavier than all the others (resembling the relationship of the top quark to the other quarks in the real world). You might demonstrate that by showing that in this model, the coupling of the "top quark" to the electroweak Higgs field is approximately 1, and that the couplings of the other "quarks" are approximately 0. Even that much can require sophisticated algebraic and geometric reasoning, and it can be easy to miss an interaction effect that would spoil those numbers.
I think we can expect this situation to improve, in a way it improves every year as new conceptual and calculational discoveries are made in the field, but we never know ahead of time how big those advances will be. Progress in string cosmology might single out part of the landscape as the place to look. Some special feature of the standard model might turn out to have very restrictive implications, again implying that only a very narrow set of vacua are worth considering. New branches of string theory might be discovered, expanding the landscape. Progress in higher mathematics might dramatically simplify the task of calculating the predicted masses to high precision.
So it's hard to say what is the real computational complexity of "searching the string landscape for the real world". At the moment, we don't have a proper algorithm for doing so, except at the qualitative level - people do write programs to search a section of the landscape for vacua containing promising grand unified models. If we knew the full extent of the landscape, and if we knew how to derive the detailed predictions for a specified vacuum, then looking for the real world could be fully automated. But string theory still contains many open problems, the solution to which could dramatically affect the difficulty of such a search.
Despite the highly unfinished nature of the theory, a few string theorists have written papers trying to guess how hard the search for the real world is. Those papers are probably the source of the idea that the search is NP-hard. But it's just a guess. There are many problems in computer science where your first idea of how to solve it is computationally very expensive, but then there's some much better algorithm that is much more efficient. Then there are problems which do appear to be intractable for all practical purposes. To say that the search for the real world in the string landscape is in the second category, is just a guess, and in my opinion not a very convincing one, because we still have a lot to learn about the math of string theory, and because we haven't yet applied all the facts we know about the real world, in order to narrow down the search space of vacua.