Think by analogy with NP. Finding the solution (the right configuration of matter) is quite difficult compared to analyzing one that's been put in front of you.
Yes, that is fair. However, I was proposing that it followed we would have found one if we could predict it based on the theory, in effect deriving the matter architecture necessary.