3 ms·
This is something I've been meaning to put together a post on, where NP problems are actually easy to solve. Take the subset sum search problem as an example, t
by hackcasual 10y ago
This is something I've been meaning to put together a post on, where NP problems are actually easy to solve. Take the subset sum search problem as an example, there's 2 "regions" of the problem space where total solutions can be done in P. If the values are either relatively small or relatively large, solving it is quite easy:
Find 23 given [1, 2, 2, 3, 1...]
Find 40 given [35, 15, 98, ...]
A lot of situations where you might give up on trying to compute an exact solution can turn out to have underlying data that makes it possible.