News for hackers. Stuff that matters.
Re:Chemical space is really big (2014) by whatshisface on Friday June 25, 2021 @06:44PM (#27637159)
I have learned over time that state space size has nothing to do with problem difficulty. Sorting finds and answer in a space with n! possibilities in n log(n) time.

Chemistry is difficult not because of the large number of chemicals but because there hasn't been a lot of structure discovered in them to allow the sort of compounding subcase solving that makes searching a sorted list tractable. The structure that has been discovered can be found in chemistry textbooks and has names like "so-and-so's rule" which can be applied to boroalkanes with between 5 and 12 vertices excepting 6, unless the cage is charged in which case you should treat it like it has one fewer vertex, unless the charge is -2 and the original vertex count is between 8 and 13, in which case...

Those rules are much better than a table as measured by information compression but you can't discover them unless you start with the table filled mostly filled out already.

Re:Chemical space is really big (2014) by jpollock on Friday June 25, 2021 @07:22PM (#27637454)
Except, 1 billion isn't typically considered _big_ to even perform full scan searches.

It's only big if it's expensive to search all of them, and that problem is very easily parallelizable.

Which makes it a $$->time equation? If it costs 1s for 1 machine to check an item, you will need 32 machines to check a billion in a year, or 12000 to search in a day.

So, it's the is_match operator that's expensive, rather than data storage? Is the match check minutes long or needing human oversight?

Re:Chemical space is really big (2014) by whatshisface on Friday June 25, 2021 @09:35PM (#27638233)
Checking a molecule can take years of computer time on a supercomputer, depending on what you are checking for. There is no upper bound to the difficulty of checking because you can always ask for a more complex situation, and you are usually asking for those situations because the simple things are usually already discovered.