SMBC Comics Forum

Welcome to the [url=https://pokemoninfinitefusion.io]Pokemon Infinite Fusion[/url] 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!

Similar to the other NP-hard issues that were covered in earlier articles, [url=https://bubble-shooters.co/]bubble shooter[/url] 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.

This post tells me more than I thought. It deserves more attention, isn't it? [url=https://heardlegame.co/]heardle[/url]

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?

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

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

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

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:

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.

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.

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

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>