Predicting When P=NP Is Resolved • Hacker News Board

Re: Predicting When P=NP Is Resolved

#61

Post by areyousure » Mon, Dec 23, 2019, 5:31 PM UTC

kevinventullo wrote: post #58

gield wrote: post #48

Earlier quoted context omitted.

>[...] I point out to them that Claude Shannon proved that generalized compression algorithms can't exist [...] What proof are you talking about?

They just mean that there is no general way to compress an arbitrary M-bit string to an N-bit string for M > N, and yet compression algorithms exist. The point is that the input to your compression is not an arbitrary M-bit string, but some very structured thing which could have a smaller representation. Similarly, when encountering what appears to be an NP-hard problem in the wild, you might still be able to find an…

One major issue is that the quote seems entirely backwards. In fact, Claude Shannon described how to optimally compress a string from a known source. https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theo... As such, Shannon's results would suggest the existence of many compression algorithms.

(And conversely, I see no reason to believe that "Claude Shannon proved that generalized compression algorithms can't exist". I assume that result predates Shannon.)

Re: Predicting When P=NP Is Resolved

#62

Post by hinkley » Mon, Dec 23, 2019, 8:54 PM UTC

areyousure wrote: post #61

kevinventullo wrote: post #58

Earlier quoted context omitted.

They just mean that there is no general way to compress an arbitrary M-bit string to an N-bit string for M > N, and yet compression algorithms exist. The point is that the input to your compression is not an arbitrary M-bit string, but some very structured thing which could have a smaller representation. Similarly, when encountering what appears to be an NP-hard problem in the wild, you might still be able to find an…

One major issue is that the quote seems entirely backwards. In fact, Claude Shannon described how to optimally compress a string from a known source. https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theo... As such, Shannon's results would suggest the existence of many compression algorithms. (And conversely, I see no reason to believe that "Claude Shannon proved that generalized compression algorithms can't e…

The pigeonhole principle establishes that you cannot fit n distinct messages into m spaces, where n>m

The Shannon coding limit defines the bounds on what subset of n can fit into a channel of capacity m, without excluding any of the others.

By drawing a fence around the possible, he fences out the impossible.

comp.compression has several longstanding bets that one particular high entropy input can not be represented by any decoder smaller than the difference in the input and output size, but I lack their confidence in the infallibility of their entropy source. It is possible someone will win that particular bet, but there will come a time where another similar bet will never be collected.

Re: Predicting When P=NP Is Resolved

#63

Post by hinkley » Mon, Dec 23, 2019, 10:24 PM UTC

fovc wrote: post #54

hinkley wrote: post #25

Earlier quoted context omitted.

One of the things that slows scientific progress is the lack of cross-discipline learning. Every so often you hear about someone taking an old concept from another field and applying it. Quite a few breakout companies have combined interdisciplinary knowledge into one product and made a mint. So many people are affected by NP complete problems that you'd think that someone would have a problem that appeared simpler o…

https://m.xkcd.com/664/

That’s the one.

The alt text:

> Some engineer out there has solved P=NP and it's locked up in an electric eggbeater calibration routine. For every 0x5f375a86 we learn about, there are thousands we never see.