3 ms·
I am not entirely convinced by the 'most problems are exponentially hard' argument, as problem-solving often has synergistic effects - e.g. consider calculus, d
by mannykannot 9y ago
I am not entirely convinced by the 'most problems are exponentially hard' argument, as problem-solving often has synergistic effects - e.g. consider calculus, developed in solving the problem of planetary orbits, but useful for so much more.
On the other hand, trying to discern a general rule from historical data is complicated by the fact that the number of problem-solvers has been growing exponentially.
- whereismypwd 9y agoI think the better argument is that most "breakthroughs" are exponentially hard, or we wouldn't consider them breakthroughs!
- mannykannot 9y ago'Exponential' means something more specific than 'big' or 'largest in class'.
- whereismypwd 9y agoExponential is probably the easiest way to say "a search without usable gradients in a high-dimensional problem space."
- mannykannot 9y ago'Breakthrough' means something less specific than 'a solution to a problem having a search without usable gradients in a high-dimensional problem space.' This is rather beside the point, however, as the the claim that kicked off this thread (most problems are exponentially hard) is about the difficulty of problem-solving in general, not the subset of problems that are pretty much hard by definition, in that their solution was/would be a breakthrough.