An Ancient Combinatorial Problem. Issue 6 (31st May 2022) - Berger, Marc; Winkler, Peter
Abstract: We study a 2000-year-old combinatorial problem which may be the first NP-complete problem in history. The Mishna considers two versions of the problem, giving an elegant solution to the first (amounting to a pseudo-polynomial algorithm), but only a partial solution to the second. We finish the job by giving a complete solution to the second problem as well as to a common generalization of the two, concluding that all three problems are weakly NP-complete.