News for hackers. Stuff that matters.
Re:How to solve an NP-complete problem in linear time by olliej on Friday June 21, 2019 @04:40PM (#20246154)
It sounds (towards the end) that this is saying that accepting a approximation of correct is often good enough, and that can often be made polynomial time.

Which is of course correct. There are lots of algorithms where there exist theoretical minimum complexities, but good approximations can do far better: lossy compression for example vastly beats the Shannon limit, google maps doesn’t take decades to plot a route from San Francisco to New York, etc

Re:How to solve an NP-complete problem in linear time by bottombutton on Friday June 21, 2019 @06:08PM (#20246668)
You might even luck out with those heuristics. Simulated annealing often results in the shortest/best/lowest-energy-state solution by accident.
Re:How to solve an NP-complete problem in linear time by olliej on Friday June 21, 2019 @09:03PM (#20247388)
Even simpler: ratchet up Joey quality you can easily get lossless output while technically beating Shannon (because the “average” image in information theory is noise, and even at the highest quality levels jpeg loses accuracy on them)
Re:How to solve an NP-complete problem in linear time by olliej on Saturday June 22, 2019 @04:10PM (#20251482)
Haha even better: compress images by just recording the dimensions and average color. Very high compression, and it’s correct for mono-colour images :)