Assume you have a 2-dimensional pizza with $2n$ ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, that is, your friend and you should each get exactly half of each ingredient. How many cuts do you need? It was recently shown using topological methods that $n$ cuts always suffice. In this work, we study the computational complexity of finding such $n$ cuts. Our main result is that this problem is PPA-complete when the ingredients are represented as point sets. For this, we give a new proof that for point sets $n$ cuts suffice, which does not use any topological methods. We further prove several hardness results as well as a higher-dimensional variant for the case where the ingredients are well-separated.
翻译:假设你有一个2维比萨饼, 配有2n美元成份, 你愿意与朋友分享。 对于这一点, 你允许用几条直切, 将披萨切开, 然后将每一秒都分给朋友。 您想要公平这样做, 也就是说, 您的朋友和您应该每人得到每个成份的一半。 您需要多少切口? 最近用地形学方法显示, 削减一美元就足够了。 在这项工作中, 我们研究找到这种减价的计算复杂性。 我们的主要结果是, 当成分被标为点数时, 问题就是 PPA 完成 。 为此, 我们给出一个新的证据, 点设定 $n 的减价足够, 但不使用任何表面学方法 。 我们进一步证明一些硬性结果, 以及一个高维变量, 用于那些成分均匀分的案例 。