Timeline for Examples of ubiquitous objects that are hard to find?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 31, 2013 at 22:36 | history | made wiki | Post Made Community Wiki by S. Carnahan♦ | ||
| Dec 31, 2013 at 18:15 | history | edited | Timothy Chow | CC BY-SA 3.0 |
Added link to paper
|
| Dec 31, 2013 at 18:09 | comment | added | Timothy Chow | @Dustin: Yes, although these sorts of examples perhaps stretch the definition of "with high probability" a bit too far. The examples I mentioned at least have probabilistic proofs of existence. | |
| Dec 31, 2013 at 11:00 | comment | added | Dustin G. Mixon | I feel like (b) comes up quite a bit in complexity theory. Take any "hard" instance of an NP-complete problem whose answer is "yes" and try to find a certificate. For example, find a clique of size $n^\epsilon$ that the devil hid in an ER graph with $p=1/2$. | |
| Dec 31, 2013 at 5:20 | history | answered | Timothy Chow | CC BY-SA 3.0 |