Pizza Sharing Is PPA-Hard
Authors: Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos4957-4965
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPAhard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPAhardness results apply 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. We also prove that decision variants of the square-cut problem are hard: the approximate problem is NP-complete, and the exact problem is ETR-complete. |
| Researcher Affiliation | Academia | Royal Holloway University of London, UK, University of Liverpool, UK, University of Essex, UK |
| Pseudocode | No | The paper focuses on theoretical proofs and complexity results and does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements about releasing source code or links to a code repository. This is a theoretical paper, and thus, code release is not typically part of its scope. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with datasets. It defines 'mass distributions' conceptually for its theoretical analysis but does not use actual training data. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not report on any empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not report on any empirical experiments that would require detailing software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experiments or their setup, such as hyperparameters or training configurations. |