Re:The undeserved status of the pigeon-hole principle (1991)
by coldtea on Sunday July 05, 2020 @07:16AM
(#23737900)
>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)
by andrepd on Saturday July 04, 2020 @07:56PM
(#23735720)
SAT solvers overwhelmingly don't use resolution. Modern state of the art solvers use DPLL/CDCL.
Re:The undeserved status of the pigeon-hole principle (1991)
by 53x15 on Saturday July 04, 2020 @08:52PM
(#23735912)
I think neel_k was referring to the fact that when a DPLL or CDCL solver concludes UNSAT you can take the trace its backtracking activity and rewrite it from the bottom up as a resolution refutation. So in this sense the solvers are finding resolution proofs.
Re:The undeserved status of the pigeon-hole principle (1991)
by CJefferson on Sunday July 05, 2020 @05:05AM
(#23737476)
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)
by ogogmad on Saturday July 04, 2020 @06:10PM
(#23735268)
Do you have a reference for 2? Thanks.
Re:The undeserved status of the pigeon-hole principle (1991)
by neel_k on Saturday July 04, 2020 @06:13PM
(#23735282)
Willie Wong wrote a nice blog post about this a while ago:
https://williewong.wordpress.com/2010/03/18/compactness-part...
Re:The undeserved status of the pigeon-hole principle (1991)
by tprice7 on Saturday July 04, 2020 @06:54PM
(#23735464)
The fact that every infinite sequence of points in a compact metric space has a cluster point is sort of like the pigeonhole principle. The grandparent comment in my opinion makes much more sense if the phrase "a compactness for metric spaces" is replaced by "sequential compactness for metric spaces".
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 for them. It also makes the question of when propositional proof systems can be more succinct than one another is also a fundamental question in complexity theory.
2. It also arises in geometry: a compactness for metric spaces is essentially the statement that the pigeonhole principle applies to the space.
I don't have a unified perspective of these two facts, but either one of them is really striking. As a result I'm okay with giving the pigeonhole principle its own natural language name.