Square-Cut Pizza Sharing is PPA-complete
share
We study the computational complexity of computing solutions for the square-cut pizza sharing problem. In this problem, we have n mass distributions in the plane, and the task is to find a path that uses horizontal and vertical segments that splits each of the masses in half while making at most n-1 turns. We show that finding an approximate solution to this problem is PPA-complete, while finding an exact solution is FIXP-hard and in BU. Our PPA-hardness result applies even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. When the path is restricted to have at most n-2 turns, we show that the approximate problem becomes NP-complete, and the exact problem becomes ETR-complete.
READ FULL TEXT