So you have a pizza with n different toppings and you want to share it with a friend so that you each get the same amount of each topping. How many cuts do you need to make?

This is a practical problem  - you might not want to share a pizza in this overly fair way, but there are other examples where n resources are distributed over an area and you might want to find a way to divide them up equally. It is also esoteric because it involves a consideration of topology and other mathematical ideas. If you want the details read the arXiv paper by Patrick Schnider of the University of Copenhagen. This is just a rough outline of the generally interesting parts.

The pizza part of the problem is easy to generalize. You have a 2D area and n different things are distributed over the area. The problem is to divide the area in 2 so that there are equal amounts of each in the areas. Notice that there is nothing saying that the divisions have to be like pizza slices, they can divide the area into any shapes. For example:

In this case 6 different types of thing have been divided equally by three lines. Notice that the cuts are perhaps more complex than you might have expected and some of the blobs of "stuff" have been divided by the cuts, but many haven't. In this case just 3 cuts are necessary. In general it has been proved that 2n different type of thing can be equally shared using just n cuts. The problem is that the proofs are existence proofs and don't give an algorithm for finding the division.

If you think about it for a moment you can see that the search for suitable lines is going to be time-consuming. However, you can also probably see that if I give you a claimed solution to the problem you can check it in polynomial time. This suggests that the algorithm to find the division is in NP.

In fact, NP is a class of decision problems with yes/no answers. The analogous complexity class for this sort of problem is PPA, Polynomial Parity Argument. which is a subset of TFNP, the class of search problems that always have a solution and that can be checked in polynomial time. Not only is this problem in PPA, it is PPA complete and any polynomial solution to it gives a solution to all such PPA problems.

Thus, we know the problem is likely to take more than polynomial time which means your pizza is very likely to have gone cold by the time you have a solution.

The current complexity analysis doesn't reveal any amazingly good algorithms for the problem and this seems like a good project for an exploration. Personally I'll just stick to eating the pizza.

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal and yet informative way and devotes a chapter to the NP problem.

More Information

The complexity of sharing a pizza Patrick Schnider

Related Articles

New Game Dots And Polygons Is NP Hard

1×n Jigsaw Puzzles are Hard

Pancake flipping is hard - NP hard

Rubik's Cube Is Hard - NP Hard

Physics Is NP Hard

Tensor Operations Are NP Hard

Candy Crush Is Harder Than It Sounds - NP Hard

Travelling Salesman - A Movie About P=NP

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info