Hacker News new | past | comments | ask | show | jobs | submit login

a related formalism is http://en.wikipedia.org/wiki/Kolmogorov_complexity, the idea that the shortest possible program defines the complexity of the problem. Thoughts:

- you might not have seen enough cases be able to characterise the true problem, e.g. in some situation a constraint exists, but you've only seen one instance of that situation

- reusing standardized components can enable you to solve the problem more quickly (even though one-size-fits-all doesn't really fit)

- Kolmogorov complexity doesn't account for efficiency, space nor time, only that the eventual answer is correct. Efficiency often requires ugly hacks




There is a resource bounded version of Kolmogorov complexity. It might even be a more useful measure for certain things. For example, a simple enumeration can prove any arithmetical statement that can be proved, but it can take time exponential in the size of the solution. With some resource weightings you might get a better idea of how hard the problem is in actual practice.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: