3 ms·
One of the things that's rarely brought up in discussions about NP complete and NP hard problems is that they have input ranges where they require non-polynomia
by hackcasual 5y ago
One of the things that's rarely brought up in discussions about NP complete and NP hard problems is that they have input ranges where they require non-polynomial time solutions. It's difficult to speak in general, but for SSS problems, when the values are comparatively small or large, the you can use the LLL algorithm to find an exact answer in polynomial time.
- hackcasual 5y agoUsing Julia and it's LLLplus library using LLLplus show(IOContext(stdout, :limit=>false), MIME"text/plain"(), subsetsum([122,275,185,597,647,216,713,457,146,518,316,489,711,645,477,804,671,231,621,98,87],4394)) ([1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1], true) Giving a yo-yo, doll, ball, racecar, car, bear, tank, checkers, jacks, truck, pinwheel as an answer