2 ms·
Maybe (can't remember, might have never known), but not necessarily. As an example of the idea, consider the simplex algorithm as it applies to linear programmi
by hansvm 4y ago
Maybe (can't remember, might have never known), but not necessarily. As an example of the idea, consider the simplex algorithm as it applies to linear programming. It has exponential worst-case behavior, but people noticed that in practice the vast majority of interesting problems could be solved quickly. Later it was shown that all non-polynomial inputs do actually lie in some diminutive subspace.
- AnimalMuppet 4y ago"Vast majority" and "vast majority of interesting ones" may be completely different. The vast majority are just random; the vast majority of interesting ones will have some kind of structure, given by the real-world problem they represent.