[2018 10-30] Bins

Blame Quintushalls for this.

Moderator: Kimra

[2018 10-30] Bins

Postby HikaruYami » Tue Oct 30, 2018 3:05 pm


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>
Posts: 8
Joined: Wed Jun 19, 2013 11:58 pm

Re: [2018 10-30] Bins

Postby rando » Tue Oct 30, 2018 3:14 pm

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

Re: [2018 10-30] Bins

Postby Orion Guardian » Tue Oct 30, 2018 3:27 pm

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

Postby Quick Answer » Tue Oct 30, 2018 3:28 pm

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.
Quick Answer

Re: [2018 10-30] Bins

Postby peteward44 » Tue Oct 30, 2018 3:40 pm

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 :lol:

Re: [2018 10-30] Bins

Postby Scarlet Manuka » Wed Oct 31, 2018 2:54 am

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

Re: [2018 10-30] Bins

Postby ICountFrom0 » Wed Oct 31, 2018 9:38 am

I'm just glad there is an answer for that joke.

Re: [2018 10-30] Bins

Postby Khaim » Wed Oct 31, 2018 5:07 pm

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?

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

Who is online

Users browsing this forum: Majestic-12 [Bot] and 14 guests