As an amusing example, consider the Pigeonhole Principle, which says that n+1 pigeons can’t be placed into n holes, with at most one pigeon per hole. It’s not hard to construct a propositional Boolean formula Φ that encodes the Pigeonhole Principle for some fixed value of n (say, 1000). However, if you then feed Φ to current Boolean satisfiability algorithms, they’ll assiduously set to work trying out possibilities: “let’s see, if I put this pigeon here, and that one there ... darn, it still doesn’t work!” And they’ll continue trying out possibilities for an exponential number of steps, oblivious to the “global” reason why the goal can never be achieved. Indeed, beginning in the 1980s, the field of proof complexity—a close cousin of computational complexity—has been able to show that large classes of algorithms require exponential time to prove the Pigeonhole Principle and similar propositional tautologies.
Hmm. The simplex method would determine that this is infeasible in at most n steps, so I'm not sure how generalizable this result is.
(Beyond that, it seems to me that this should be solvable in one step, by assuming what you want to prove and checking for contradictions. You convert "at most one" to "one", figure out that the largest feasible number of pigeons is 1,000, which is less than 1,001 and you're done. This looks like it depends on the symmetry of the problem, though, and so for general problems you'd need to use simplex.)
While reading the answer to the question 'What is it like to have an understanding of very advanced mathematics?' I became curious about the value of intuition in mathematics and why it might be useful.
It usually seems to be a bad idea to try to solve problems intuitively or use our intuition as evidence to judge issues that our evolutionary ancestors never encountered and therefore were never optimized to judge by natural selection.
And so it seems to be especially strange to suggest that intuition might be a good tool to make mathematical conjectures. Yet people like fields medalist Terence Tao seem to believe that intuition should not be disregarded when doing mathematics,
The author mentioned at the beginning also makes the case that intuition is an important tool,
But what do those people mean when they talk about 'intuition', what exactly is its advantage? The author hints at an answer,
At this point I was reminded of something Scott Aaronson wrote in his essay 'Why Philosophers Should Care About Computational Complexity',
Again back to the answer on 'what it is like to have an understanding of very advanced mathematics'. The author writes,
Humans are good at 'zooming out' to detect global patterns. Humans can jump conceptual gaps by treating them as "black boxes".
Intuition is a conceptual bird's-eye view that allows humans to draw inferences from high-level abstractions without having to systematically trace out each step. Intuition is a wormhole. Intuition allows us get from here to there given limited computational resources.
If true, it also explains many of our shortcomings and biases. Intuitions greatest feature is also our biggest flaw.
Our computational limitations make it necessary to take shortcuts and view the world as a simplified model. That heuristic is naturally prone to error and introduces biases. We draw connections without establishing them systematically. We recognize patterns in random noise.
Many of our biases can be seen as a side-effect of making judgments under computational restrictions. A trade off between optimization power and resource use.
It it possible to correct for the shortcomings of intuition other than by refining rationality and becoming aware of our biases? That's up to how optimization power scales with resources and if there are more efficient algorithms that work under limited resources.