COPENHAGEN, Denmark — Holiday cookies shaped like reindeers, snowmen, angels, and stockings are one of many cherished traditions in households all over the world. However, sculpting these yuletide symbols while minimizing wasted dough is a Christmas riddle that mankind has struggled to answer for centuries. Now, even modern science concedes defeat.
Researchers at the University of Copenhagen say even computer algorithms can’t determine the absolute best way to cut Christmas cookies. On a broader level, study authors set out to determine the best way to pack objects in two dimensions without them overlapping. This is actually a question scientists have been trying to answer for decades too.
The packing problem
“While algorithms let us solve seriously complex problems, this is one that remains too much of a mouthful for today’s computers. For now, it isn’t possible to pack more than 5-10 objects optimally. And, our result suggests that this number probably won’t increase much for the time being,” explains Mikkel Abrahamsen, an assistant professor in the Department of Computer Science, in a university release.
The conundrum of how to pack together objects in the most optimal way applies to far more than just the holidays or home shelves. Clothing manufacturing and metal processing companies often face this dilemma. For instance, it’s imperative to cut materials while producing as little waste as possible and pack shipping containers efficiently.
The research team says they know the size of the smallest square container capable of packing up to 10 square 1×1 meter pallets. But, once you add just one more pallet to the equation, researchers can’t calculate the best size for a container.
“As more pallets are added, the calculation time increases beyond exponentially. Not even the best computers can keep up. Theoretically it’s possible. But based upon the speed at which computing power is growing, it will probably take millions of years before we are able to optimize the handling of a few additional objects,” Abrahamsen says.
Computerizing Christmas cookies? Don’t even think about it!
Christmas cookies come in a variety of shapes and sizes. So, study authors can only produce “optimal solutions” for up to four cookies.
It’s a bit surprising, for all of modern technology’s wonders, Christmas cookies seem to be a nut too tough to crack. Well, Abrahamsen says this riddle is like solving equations of degree five or higher, with tons of additional unknowns. Essentially, imagine trying to solve a complex math problem without knowing the numbers.
“Our study proves that the problem has a nature that we in mathematics refer to as continuous — which in a nutshell, means that one must know all of the coordinates at which the cookies can be placed and all of the angles at which they can be rotated,” Abrahamsen explains.
On a comforting note, at least we all know that humans are still much better than computers when it comes to making cookies – for now!
“In both industry and over the kitchen counter we must continue to be satisfied with our less-than-optimal solutions and rest assured that we humans are still better than computers for these types of tasks — for the time being,” Abrahamsen concludes.
The study is being presented at the FOCS 2020 (61st Annual IEEE Symposium on Foundations of Computer Science).