Hacker News Reader

Not explicitly listed, but obviously hard, by definition, in (theoretical) CS: NP-Hard and NP-Complete problems.

Ex:

* knapsack (fit the most “boxes” into min number of containers, sometimes 4D+ “boxes”)

* traveling salesman

I'm fascinated by problems, that are NP complete, but still can have a ton of optimizations that can reduce the time needed by many orders of magnitude (millions or more), like SAT solving. Or approximate solutions / heuristics like approx. traveling salesman. Seeing huge improvements on real-life problems, even if you know the problem is asymptotically exponential feels like you've fought against impossible odds and won.

There's a whole subfield of CS, approximation algorithms, studying what you described. Interesting indeed.

funny, how many times in my career I've encountered the knapsack problem. but I can say off-by-one hit me many more times.

Reply on news.ycombinator.com