3 ms·

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)

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.

jpollock 5y ago
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?
- whatshisface 5y ago
  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.

3 ms·

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)

by whatshisface 5y ago

jpollock 5y ago
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?
- whatshisface 5y ago
  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.