Hacker News new | ask | show | jobs
by mathattack 5359 days ago
If a sock has a hole, it gets tossed.

Now that I think of it, the mixed sock problem can actually be worse than O(n^2). For instance, if I decide that I want to wear my Marvin the Martian socks, and can only find one in the sock drawer, then it's a big problem. Look in the other drawers. Look under the bed. Look in the dryer. Repeat. Repeat. Until the other one is given up for lost.
1 comments
farnsworth 5359 days ago
It doesn't depend just on n since you aren't just searching through n available socks, you are searching k places with n_k socks in each place and with p_k confidence that you have thoroughly searched each place. I can't think of a more general problem that this might correspond to.
link
mathattack 5359 days ago
Will it get solved when we straighten out this whole P NP business?
link