4 ms·
Scott Aaronson (himself a harsh Penrose critic on these matters!) had made this point several years ago, but in the context of 3SAT (an NP-complete problem). Hi
by SilasX 10y ago
Scott Aaronson (himself a harsh Penrose critic on these matters!) had made this point several years ago, but in the context of 3SAT (an NP-complete problem). His "human favoring instance" was a 3SAT problem that encodes a violation of the pigeonhole principle.
Then [1], as now, I think that was still too generous to humans -- both Penrose and Aaronson have spent so much time around smart people that they've forgotten what the average person is like. The average person isn't clever enough, especially when even 4 pigeon/3 hole instances blow up to an absurd number of clauses.
Either way, I think the scaling problem rears its head:
- Only an exponentially small fraction of problems is pathological like this.
- Only an exponentially small fraction of humans can derive these theorems on the fly that simplify the problem.
- You can get everyone can solve it, but only by providing an exponentially precise hint. (The "good heuristic oracle" in the linked thread.)
Plus, I suspect there are general heuristics that avoid much of these "dumb" searches, for example if you represent the problem in a graph and check its symmetries to avoid loops of "hm, but what if I put pigeons 2, 3, and 4 in the holes... blast, that doesn't work either."
[1] https://philtcs.wordpress.com/2011/10/06/class-4-the-p-vs-np-problem-human-mathematical-creativity-and-knowledge-of-numbers/#comment-136 https://philtcs.wordpress.com/2011/10/06/class-4-the-p-vs-np...
- CJefferson 10y agoYes, most decent modern SAT solvers have no trouble with the pigeonhole problem.
- skj 10y agoNit: "exponentially" does not mean "really", as in "really small". It means increasing (or decreasing) at a far faster rate than what it's exponential with. Often time, but any metric can be used.
- SilasX 10y agoThat ("has exp(n) scaling with respect to input size") is how I was using it, and that usage is a critical part of my point, that the involvement of humans does not change the problem's difficulty class. If you have a reason to think that it is not literally exponential, I'd love to discuss that! (I have good reasons to believe this is the actual behavior on the first and third effects but not necessarily the second.)
- umanwizard 10y agoNo, it actually doesn't mean anything about far faster. It means the rate of increase is linearly related to the current value.
- hackcasual 10y agoYou touch on something interesting that I don't see often mentioned with NP-hard problems, and that's the actual inputs for where they're hard. Packing a knapsack with many small items or items large relative to the knapsack make it relatively trivial. It's often the case that NP real world problems actually have their inputs fall in the easier to solve ranges.
- SilasX 10y ago>Packing a knapsack with many small items or items large relative to the knapsack make it relatively trivial. Interestingly, that's the basis of the (now broken) Knapsack cryptosystem -- your private key is an easy knapsack, and you convert it to the public key -- a hard knapsack -- via modular multiplication. You encode your message by your choice of which items from the hard knapsack to add to the sum, which becomes the ciphertext. https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
- hackcasual 10y agoHave you checked out lattice based crypto? It's the spiritual successor to merkel-hellman, based on the hardness of subset sum. I've got a rough presentation from when I talked about it at a reading group: https://docs.google.com/presentation/d/1_kLJ7M_7HKrzN0auz0-zOLImqzhhX9TX8xrQA71zwNA/edit?usp=sharing https://docs.google.com/presentation/d/1_kLJ7M_7HKrzN0auz0-z...
- SilasX 10y agoInteresting! I didn't know they were related. Thanks!