The undeserved status of the pigeon-hole principle (1991) • Hacker News Board

Re: The undeserved status of the pigeon-hole principle (1991)

#21

Post by morelisp » Sun, Jul 05, 2020, 7:08 AM UTC

atq2119 wrote: post #20

bloaf wrote: post #18

Earlier quoted context omitted.

I agree. I've seen some marvelous pigeon hole explanations of why you cannot write a general lossless compression algorithm that makes all files smaller. I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand.

That's really more about surjectivity and simple counting. Neither the pigeon hole principle not a max/average argument are really necessary. Say you're trying to find a way to compress every n+1 bit string into an n bit string. Losslessness means that you have to come up with a function d from n bit string to n+1 bit string that decompresses. The number of n+1 bit string is larger, so there must be n+1 bit strings t…

This is still the pigeonhole principle, just inverted - If you have more holes than pigeons (and you can’t make fractional or quantum pigeons) at least one hole must have no pigeons.

Re: The undeserved status of the pigeon-hole principle (1991)

#22

Post by [deleted] » Sun, Jul 05, 2020, 7:09 AM UTC

atq2119 wrote: post #20

bloaf wrote: post #18

Earlier quoted context omitted.

I agree. I've seen some marvelous pigeon hole explanations of why you cannot write a general lossless compression algorithm that makes all files smaller. I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand.

That's really more about surjectivity and simple counting. Neither the pigeon hole principle not a max/average argument are really necessary. Say you're trying to find a way to compress every n+1 bit string into an n bit string. Losslessness means that you have to come up with a function d from n bit string to n+1 bit string that decompresses. The number of n+1 bit string is larger, so there must be n+1 bit strings t…

[deleted]

Re: The undeserved status of the pigeon-hole principle (1991)

#23

Post by hbogert » Sun, Jul 05, 2020, 8:38 AM UTC

I hardly ever disagree with the man, but as long as at least 50% of freshman get this wrong in introductionary lectures of fundamental logic, a named principle is very appropriate imo.

Re: The undeserved status of the pigeon-hole principle (1991)

#24

Post by CJefferson » Sun, Jul 05, 2020, 9:05 AM UTC

andrepd wrote: post #12

neel_k wrote: post #5

This note represents a rare misstep by Dijkstra: the pigeonhole principle actually is a special and important principle worthy of a special name of its own. For example: 1. When you formulate the pigeonhole principle in propositional logic, its resolution proofs are exponentially large. Since modern SAT solvers are basically very fancy propositional resolution provers, this gives you a nice way to find hard instances…

SAT solvers overwhelmingly don't use resolution. Modern state of the art solvers use DPLL/CDCL.

While they indeed don't use resolution directly, DPLL/CDCL is in many ways equivalent.

Most modern SAT solvers will still have trouble with the pigeon-hole style problems (although some have inbuilt explicit detection, or symmetry breaking, which will let them solve it efficiently).

Re: The undeserved status of the pigeon-hole principle (1991)

#25

Post by jimhefferon » Sun, Jul 05, 2020, 10:38 AM UTC

pinewurst wrote: post #10

jmount wrote: post #4

I feel this is an instance of prof.dr. Edsger W.Dijkstra just being mean. If one works more on pigeon-hole principles you end up with Ramsey Theory, which covers some amazing results.

It wouldn’t be the only one. Review his archived papers and they’re well salted with snark.

"Arrogance in computer science is measured in nano-Dijkstra's" - Alan Kay (https://youtu.be/9KivesLMncs)

(I usually like Dijkstra's works but the quote does make a person smile.)

Re: The undeserved status of the pigeon-hole principle (1991)

#26

Post by coldtea » Sun, Jul 05, 2020, 11:16 AM UTC

neel_k wrote: post #5

This note represents a rare misstep by Dijkstra: the pigeonhole principle actually is a special and important principle worthy of a special name of its own. For example: 1. When you formulate the pigeonhole principle in propositional logic, its resolution proofs are exponentially large. Since modern SAT solvers are basically very fancy propositional resolution provers, this gives you a nice way to find hard instances…

>This note represents a rare misstep by Dijkstra

Rare? He was often biased by his preferences, teaching styles, and opinions, in his notes, as opposed to pure science/logic.

Re: The undeserved status of the pigeon-hole principle (1991)

#27

Post by phaemon » Sun, Jul 05, 2020, 11:34 AM UTC

bloaf wrote: post #18

starchild_3001 wrote: post #13

I (or any math noob) can easily understand the pigeon hole principle. His more detailed arguments about max, avg and a bunch of other stuff is more obtuse and harder to follow. IMO, pigeon hole principle, where applicable, wins this argument. If you're dealing with a sequence of real numbers, you might need max >= avg.

I agree. I've seen some marvelous pigeon hole explanations of why you cannot write a general lossless compression algorithm that makes all files smaller. I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand.

A "file" on a computer is just a number.

When you compress a file, you are representing a big number with a small number.

There are more big numbers than there are small numbers.

Re: The undeserved status of the pigeon-hole principle (1991)

#28

Post by HelloNurse » Sun, Jul 05, 2020, 11:37 AM UTC

Since a proof is a proof, the methods are a matter of taste. Driving away from pontless reductio ad absurdum arguments is a good thing, but sometimes putting in the spotlight the object that need to be matched or counted instead of bare numbers can be useful. For instance, in the ranch example I'd ensure that I'm counting correctly by considering the cowboys and horses in the connected components of the bipartite graph whose edges represent exclusive horse ownership: each connected component contains 0 or 1 cowboys and 1 or more horses.

Re: The undeserved status of the pigeon-hole principle (1991)

#29

Post by [deleted] » Sun, Jul 05, 2020, 11:38 AM UTC

neel_k wrote: post #5

This note represents a rare misstep by Dijkstra: the pigeonhole principle actually is a special and important principle worthy of a special name of its own. For example: 1. When you formulate the pigeonhole principle in propositional logic, its resolution proofs are exponentially large. Since modern SAT solvers are basically very fancy propositional resolution provers, this gives you a nice way to find hard instances…

[deleted]

Re: The undeserved status of the pigeon-hole principle (1991)

#30

Post by atq2119 » Sun, Jul 05, 2020, 11:42 AM UTC

morelisp wrote: post #21

atq2119 wrote: post #20

Earlier quoted context omitted.

That's really more about surjectivity and simple counting. Neither the pigeon hole principle not a max/average argument are really necessary. Say you're trying to find a way to compress every n+1 bit string into an n bit string. Losslessness means that you have to come up with a function d from n bit string to n+1 bit string that decompresses. The number of n+1 bit string is larger, so there must be n+1 bit strings t…

This is still the pigeonhole principle, just inverted - If you have more holes than pigeons (and you can’t make fractional or quantum pigeons) at least one hole must have no pigeons.

It's similar, but that's not usually referred to as the pigeon hole principle.