Yes, but the search space is mind boggling.

How so? Just a function of all the different atoms and sub-atomic particles interacting?

I'll link to another reply of mine: https://news.ycombinator.com/item?id=36966474

The "just a function of" is a non-trivial problem. Given a single set of elements you want to "try out" results in a huge global optimization problem to find the set of stable structures (low energy). When aided by experimental data it becomes a tractable problem.

Not really. Think of this as being analogous to public key/private key crypto; it's easy to check a signature (simulate a structure), it's extremely hard to forge one (design a new material ab initio).