## [2018 10-30] Bins

Blame Quintushalls for this.

Moderator: Kimra

### [2018 10-30] Bins

https://www.smbc-comics.com/comic/bins

I actually haven't seen a bin-packing joke like this before and was very amused. Unfortunately, the mathematician failed to account for the fact that the mover can have a small and more importantly *constant* number of constantly-sized bins and that the breadth of people he has moved will have, in the grand scheme of things, a small number of objects to be moved.

It turns out that when n is sufficiently small, even exponential-time algorithms can be run quickly. As of 2003, an algorithm had been developed that even on very average hardware of the day could consistently find optimal solutions for 80 items in an average of 31 milliseconds. It obviously continues to grow quickly from there, but it's not unreasonable for a mover to expect people to batch their smallest items before having them shove everything into a truck. A mover isn't going to literally pick up your silverware for you.

<this is where someone tries to point out that the complexity of the problem increases when the size of the items is expressed in arbitrary-precision values, and I retort by pointing out that that precision only matters on real hardware, which a mathematician wouldn't give a shit about>

<this is where someone correctly points out that the shape of the objects matters in a real solution of packing three-dimensional bins, and I point out that that ruins the entire joke about the bin-packing problem from the perspective of the mathematician>
HikaruYami

Posts: 8
Joined: Wed Jun 19, 2013 11:58 pm

### Re: [2018 10-30] Bins

Can you explain how this joke (presumably) relates packing algorithms to cracking internet security?
rando

### Re: [2018 10-30] Bins

One of the really complex algorithms is taking a number of items and arranging them in the most efficient way possible. It is a variant of the salesman-problem.

So the mathematician concludes: the mover can solve an algorithm that gets exponentially more complex the more items are included at a glance (i.e. very fast)

Bruteforcing a password would be child's play like that.
Orion Guardian

### Re: [2018 10-30] Bins

The a short answer since I am on my phone is that what the mover can do is solve the bin packing problem instantly. The bin packing problem is NP hard. If you can algorithmically solve one NP hard problem you can solve them all so in theory he could instantly solve all np hard problems. Computer security and all of cryptography relies on solving NP hard problems to be very slow.

### Re: [2018 10-30] Bins

According to Google, 900 times the mass of the Great Pyramid of Giza would fit into a teaspoon if it were the density of a neutron star. So they must have a LOT of stuff to be the size of a baseball
peteward44

### Re: [2018 10-30] Bins

HikaruYami wrote:https://www.smbc-comics.com/comic/bins
It turns out that when n is sufficiently small, even exponential-time algorithms can be run quickly.

That's why the word "instantly" is critical to the joke. Of course the mathematician takes it literally
Scarlet Manuka

ICountFrom0

### Re: [2018 10-30] Bins

It took my brain a second to context switch to get to joke, but it got a hearty laugh once I did.

My question is, what blog post was Zach reading?
Khaim

Return to Latest Comic Discussion 3: Revenge of the Son of Latest Comic Discussion 2

### Who is online

Users browsing this forum: No registered users and 11 guests