3 ms·
Not explicitly listed, but obviously hard, by definition, in (theoretical) CS: NP-Hard and NP-Complete problems. Ex: * knapsack (fit the most “boxes” into mi
by bfung 4y ago
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
- Dzugaru 4y agoI'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.
- karmakurtisaani 4y agoThere's a whole subfield of CS, approximation algorithms, studying what you described. Interesting indeed.
- _glass 4y agofunny, how many times in my career I've encountered the knapsack problem. but I can say off-by-one hit me many more times.