[mannykannot]

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]

I think the better argument is that most "breakthroughs" are exponentially hard, or we wouldn't consider them breakthroughs!

[mannykannot]

'Exponential' means something more specific than 'big' or 'largest in class'.

[whereismypwd]

Exponential is probably the easiest way to say "a search without usable gradients in a high-dimensional problem space."

[mannykannot]

'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.