[2018 10-30] Bins

Blame Quintushalls for this.

Moderators: NeatNit, Kimra

HikaruYami
Posts: 16
Joined: Wed Jun 19, 2013 11:58 pm

[2018 10-30] Bins

Post by HikaruYami »

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>

rando

Re: [2018 10-30] Bins

Post by rando »

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

Orion Guardian

Re: [2018 10-30] Bins

Post by Orion Guardian »

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.

Quick Answer

Re: [2018 10-30] Bins

Post by Quick Answer »

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.

peteward44

Re: [2018 10-30] Bins

Post by peteward44 »

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:

Scarlet Manuka

Re: [2018 10-30] Bins

Post by Scarlet Manuka »

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

ICountFrom0

Re: [2018 10-30] Bins

Post by ICountFrom0 »

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

Khaim

Re: [2018 10-30] Bins

Post by Khaim »

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?

henny12

Re: [2018 10-30] Bins

Post by henny12 »

This post tells me more than I thought. It deserves more attention, isn't it? heardle

Miranda23

Re: [2018 10-30] Bins

Post by Miranda23 »

Similar to the other NP-hard issues that were covered in earlier articles, bubble shooter the bin packing problem falls under this category. A set of objects of varying sizes must be packed into bins of a specific size while ensuring that the fewest possible bins are used.

helendam23

Re: [2018 10-30] Bins

Post by helendam23 »

Welcome to the Pokemon Infinite Fusion revolution, where every fusion is a masterpiece waiting to be born, and every Trainer is an artist shaping the future of Pokemon. Your fusion adventure begins now!

Post Reply