This is why even mathematicians struggle to use all of their cookie dough
This is an Inside Science story.
It's time for one of the biggest decisions of the year: How should you cut Christmas cookies from a sheet of cookie dough while wasting as little as possible?
Home bakers can perhaps take solace in learning that this is a problem that puzzles even professional mathematicians. Now new research shows that efficiently placing shapes such as gingerbread men, stars or Christmas trees without wastage is a much more difficult problem than is often assumed.
Mikkel Abrahamsen at the University of Copenhagen and his colleagues have mathematically proven that the "packing problem" of finding the best pattern to cut out cookies can be as computationally laborious as solving a class of extremely tricky algebraic equations that even supercomputers can't always solve in any reasonable amount of time. He presented the research at the FOCS 2020 conference last month.
The more cookies you want to cut out, and the more complex their shape is, the harder the problem becomes.
In the parlance of mathematicians and computer scientists, these especially difficult problems are called "∃R-complete" -- but researchers don't agree how that phrase should be pronounced: "It's actually an abbreviation for 'existential theory of the reals,'" Abrahamsen said.
∃R-complete problems can be much harder to solve than the class of problems known as "NP-complete," which are themselves quite difficult -- and it was assumed packing problems fell into the NP class.
The new study shows some packing problems are even more difficult than commonly thought, said Abrahamsen.
Mathematicians have been investigating packing problems for more than 100 years, and computer scientists have joined them in recent decades.
Finding the best way to cut sewing patterns from strips of cloth would have been an early application -- as would cutting out cookies -- but packing problems also have modern applications in packaging, storage and the complex patterns used to cut metals, ceramics and plastics for industrial designs.
"I think packing problems are appealing to mathematicians and computer scientists because they seem very simple -- just place these items into the container," said researcher and artist Erik Demaine, a professor at the Massachusetts Institute of Technology who was not involved in the latest research. "Yet they tend to be extremely complicated to actually solve."
Abrahamsen and his colleagues achieved their proof with software tools they used to investigate a related mathematical mystery called the "art gallery problem," where a certain number of security guards or cameras must be placed within a space so that they can keep watch on all of the artwork on the walls.
"We had some experience from that problem on how to prove these things," he said. "And then we found out that we could actually use similar tools for this packing problem."
The upshot of their work is that packing problems, like cutting Christmas cookies from a sheet of dough, can be really hard -- even for computers. Sometimes humans can do better with experience and intuition. Employees called "nesters" in the fashion industry are sometimes able to outperform computers to find the best fit, although computers are usually used to find a "close enough" solution and save time, Abrahamsen said.
Abrahamsen said his research had caused him to see packing problems everywhere, such as when he was stacking food in a cupboard or packing a suitcase. "And then I realize that I shouldn't think too much about it, because I know that I probably won't find an optimal solution," he said.
The implications of the new research will probably be most felt in hard mathematics: "[It's] a technical tour de force, and a pleasing result," said computer scientist Marcus Schaefer at DePaul University in Chicago, who was not involved in the study but who has pondered ∃R-complete problems in his own work.
For MIT's Demaine, the research may influence the mathematics of computational origami design -- a field named for the Japanese art of paper folding, with applications in architecture, civil engineering, space, medicine and robotics.
Computational origami involves a central packing problem, and research by Demaine and his colleagues shows it is "NP-hard," he said. "But now I wonder whether it is ∃R-hard as well," he said.
Inside Science is an editorially independent nonprofit print, electronic and video journalism news service owned and operated by the American Institute of Physics.
